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

Abstract

A $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.