Degree Type

Dissertation

Date of Award

2017

Degree Name

Doctor of Philosophy

Department

Mathematics

Major

Mathematics

First Advisor

Berard Lidicky

Second Advisor

Steve Butler

Abstract

We consider two branches of coloring problems for graphs: list coloring and packing coloring. We introduce a new variation to list coloring which we call choosability with union separation: For a graph G, a list assignment L to the vertices of G is a (k,k+t)-list assignment if every vertex is assigned a list of size at least k and the union of the lists of each pair of adjacent vertices is at least k+t. We explore this new variation and offer comparative results to choosability with intersection separation, a variation that has been studied previously.

Regarding packing colorings, we consider infinite lattice graphs and provide bounds to their packing chromatic numbers. We also provide algorithms for coloring these graphs. The lattices we color include two-layer hexagonal lattices as well as the truncated square lattice, a 3-regular lattice whose faces have length 4 and 8.

DOI

https://doi.org/10.31274/etd-180810-5276

Copyright Owner

Kevin Moss

Language

en

File Format

application/pdf

File Size

116 pages

Share

COinS