##
Coloring problems in graph theory

##### Date

##### Authors

##### Major Professor

##### Advisor

##### Committee Member

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

##### Authors

##### Research Projects

##### Organizational Units

##### Journal Issue

##### Is Version Of

##### Versions

##### Series

##### Department

##### Abstract

In this thesis, we focus on variants of the coloring problem on graphs. A coloring of a graph $G$ is an assignment of colors to the vertices. A coloring is proper if no two adjacent vertices are assigned the same color. Colorings are a central part of graph theory and over time many variants of proper colorings have been introduced. The variants we study are packing colorings, improper colorings, and facial unique-maximum colorings.

A packing coloring of a graph $G$ is an assignment of colors $1, \ldots, k$ to the vertices of $G$ such that the distance between any two vertices that receive color $i$ is greater than $i$. A $(d_1, \ldots, d_k)$-coloring of $G$ is an assignment of colors $1, \ldots, k$ to the vertices of $G$ such that the distance between any two vertices that receive color $i$ is greater than $d_i$. We study packing colorings of multi-layer hexagonal lattices, improving a result of Fiala, Klav\v{z}ar, and Lidick\'{y}, and find the packing chromatic number of the truncated square lattice. We also prove that subcubic planar graphs are $(1, 1, 2, 2, 2)$-colorable.

A facial unique-maximum coloring of $G$ is an assignment of colors $1, \ldots, k$ to the vertices of $G$ such that no two adjacent vertices receive the same color and the maximum color on a face appears only once on that face. We disprove a conjecture of Fabrici and G\"{o}ring that plane graphs are facial unique-maximum $4$-colorable. Inspired by this result, we also provide sufficient conditions for the facial unique-maximum $4$-colorability of a plane graph.

A $\{ 0, p \}$-coloring of $G$ is an assignment of colors $0$ and $p$ to the vertices of $G$ such that the vertices that receive color $0$ form an independent set and the vertices that receive color $p$ form a linear forest. We will explore $\{ 0, p \}$-colorings, an offshoot of improper colorings, and prove that subcubic planar $K_4$-free graphs are $\{ 0, p \}$-colorable. This result is a corollary of a theorem by Borodin, Kostochka, and Toft, a fact that we failed to realize before the completion of our proof.