Electronic Theses and Dissertations

Equitable Block-Colorings of Graph-Decompositions and Tiling Generalized Petersen Graphs

﻿
dc.contributor.authorMatson, Elizabeth
dc.date.accessioned2018-04-23T21:08:55Z
dc.date.available2018-04-23T21:08:55Z
dc.date.issued2018-04-23
dc.identifier.urihttp://hdl.handle.net/10415/6136
dc.description.abstractA $C_4$-decomposition of $K_v - F$, where $F$ is a $1$-factor of $K_v$ and $C_4$ is the cycle on $4$ vertices, is a partition $P$ of $E(K_v - F)$ into sets, each element of which induces a $C_4$ (called a block). A function assigning a color to each block defined by $P$ is said to be an $(s,p)$-equitable block-coloring if: exactly $s$ colors are used; each vertex $v$ is incident with blocks colored with exactly $p$ colors; and the blocks containing $v$ are shared out as evenly as possible among the $p$ color classes. We introduce the study of the structure of such colorings, defining the color vector $V(E)=(c_1(E), c_2(E),$ $\dots, c_s(E))$ of an $(s,p)$-equitable block-coloring $E$ of $G$, arranged in non-decreasing order, where $c_i(E)$ is the number of vertices in $G$ incident with a block of color $i$. In all cases where $\chi'_p(v) > p$, the most interesting values of $V(E)$ are considered, namely $c_1(E)$ and $c_s(E)$. The problems of finding the value of the smallest color class when it is as large as possible, $\overline{\psi'_1}(C_4,K_v - F)$, and the value of the largest color class when it is as small as possible, $\psi'_s(C_4,K_v - F)$, are settled. We then consider the opposite extremes, solving the problems of finding the value of the smallest color class when it is as small as possible, $\psi'_1(C_4,K_v - F)$, and the value of the largest color class when it is as large as possible, $\overline{\psi'_s}(C_4,K_v - F)$. These extreme colorings follow from another interesting problem, namely finding $(s,p)$-equitable edge-colorings of $K_v$. The most interesting values are $\psi'_1(K_2,K_{v/2})$, $\overline{\psi'_{s}}(K_2,K_{v/2})$, $\psi'_1(C_4,K_{v}-F)$ and $\overline{\psi'_{s}}(C_4,K_{v}-F)$, but as a bonus from our method of proof in Chapter \ref{particulartypes2}, we settle the value of $\overline{\psi'_{i}}(K_2,K_{v/2})$ and $\overline{\psi'_{i}}(C_4,K_{v}-F)$ for all other values of $i$ as well. Finally, some work on tiling generalized Petersen graphs, $P(n,k)$, with paths consisting of two and four vertices is also presented along with our plans for future work with tiling with paths on six and eight vertices.en_US
dc.rightsEMBARGO_GLOBALen_US
dc.subjectMathematics and Statisticsen_US
dc.titleEquitable Block-Colorings of Graph-Decompositions and Tiling Generalized Petersen Graphsen_US
dc.typePhD Dissertationen_US
dc.embargo.lengthMONTHS_WITHHELD:60en_US
dc.embargo.statusEMBARGOEDen_US
dc.embargo.enddate2023-04-19en_US
dc.contributor.committeeMcDonald, Jessica
dc.contributor.committeeHoffman, Dean
dc.contributor.committeeJohnson, Peter
dc.creator.orcid0000-0002-5214-9785en_US