Coloring problems in graph theory: k-packings and (p,q)-colorings
Date
2024-05
Authors
McRoberts, Christian
Major Professor
Advisor
Lidicky, Bernard
Herzog, David P
Hogben, Leslie
Song, Sung Y
Rossmanith, James
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
A graph coloring is a map $\varphi$ from the vertices (or edges) of a graph $G$ to a set of colors. In Chapters 1 and 2, we provide preliminary information about graph theory and graph colorings and offer motivation behind the work.
In Chapter 3, we consider the packing chromatic number of the $n$-layered infinite truncated square lattice, denoted $\mathcal{S}_{Tr} \square P_n$. Given a graph $G,$ an \textbf{$i$-packing} is a set $X \subseteq G$ where $d(u,v) > i$ for every $u,v \in X.$ A \textbf{$k$-packing} of $G$ is a proper coloring of the vertices into classes $X_1, \ldots, X_k$ such that $X_i$ is an $i$-packing. The least such $k$ is called the \textbf{packing chromatic number} of $G$ and is denoted $\chi_\rho(G).$ We show that $\chi_\rho(\mathcal{S}_{Tr} \square P_n) = \infty$ for $n \geq 4.$
In Chapter 4, we consider $(p,q)$-colorings. For fixed integers $p \text{ and } q$, a \textbf{$(p,q)$-coloring} is an edge-coloring of $K_n$ such that every induced subgraph on $p$ vertices receives at least $q$ colors. The $(p,q)$ function, $f(n,p,q) = k,$ denotes the least number of colors required for a $(p,q)$-coloring of $K_n.$ We define the inverted $(p,q)$ function, denoted $f^{-1}(k,p,q) = n,$ as the maximum number of vertices required for a $(p,q)$-coloring of $K_n$ to exist in $k$ colors. We provide bounds for small values of $k,p \text{ and } q:$ $f^{-1}(3,4,3) = 9; 13 \leq f^{-1}(3,5,3) \leq 22; 16 \leq f^{-1}(3,6,3) \leq 53; 13 \leq f^{-1}(4,4,3) \leq 17; \text{ and } f^{-1}(4,4,4) = 9.$
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation