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

Language

en

File Format

application/pdf

File Size

88 pages

Included in

Mathematics Commons

Share

COinS