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

Metadata Field | Value | Language |
---|---|---|

dc.contributor.advisor | Rodger, Chris | |

dc.contributor.author | Matson, Elizabeth | |

dc.date.accessioned | 2018-04-23T21:08:55Z | |

dc.date.available | 2018-04-23T21:08:55Z | |

dc.date.issued | 2018-04-23 | |

dc.identifier.uri | http://hdl.handle.net/10415/6136 | |

dc.description.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. | en_US |

dc.rights | EMBARGO_GLOBAL | en_US |

dc.subject | Mathematics and Statistics | en_US |

dc.title | Equitable Block-Colorings of Graph-Decompositions and Tiling Generalized Petersen Graphs | en_US |

dc.type | PhD Dissertation | en_US |

dc.embargo.length | MONTHS_WITHHELD:60 | en_US |

dc.embargo.status | EMBARGOED | en_US |

dc.embargo.enddate | 2023-04-19 | en_US |

dc.contributor.committee | McDonald, Jessica | |

dc.contributor.committee | Hoffman, Dean | |

dc.contributor.committee | Johnson, Peter | |

dc.creator.orcid | 0000-0002-5214-9785 | en_US |