#### Degree Type

Dissertation

#### Date of Award

2018

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### Major

Mathematics

#### First Advisor

Bernard Lidicky

#### 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.

#### Copyright Owner

Kacy Messerschmidt

#### Copyright Date

2018-08

#### Language

en

#### File Format

application/pdf

#### File Size

88 pages

#### Recommended Citation

Messerschmidt, Kacy, "Coloring problems in graph theory" (2018). *Graduate Theses and Dissertations*. 16639.

https://lib.dr.iastate.edu/etd/16639