Coloring problems in graph theory

Date
2017-01-01
Authors
Moss, Kevin
Major Professor
Advisor
Berard Lidicky
Steve Butler
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
Source