Degree Type
Dissertation
Date of Award
2012
Degree Name
Doctor of Philosophy
Department
Mathematics
First Advisor
Maria Axenovich
Abstract
Graph coloring is a well-known and well-studied area of graph theory that has many applications. In this dissertation, we look at two generalizations of graph coloring known as list-coloring and sum-list-coloring. In both of these types of colorings, one seeks to first assign palettes of colors to vertices and then choose a color from the corresponding palette for each vertex so that a proper coloring is obtained.
A celebrated result of Thomassen states that every planar graph can be properly colored from any arbitrarily assigned palettes of five colors. This result is known as 5-list-colorability of planar graphs. Albertson asked whether Thomassen's theorem can be extended by precoloring some vertices which are at a large enough distance apart. Hutchinson asked whether Thomassen's theorem can be extended by allowing certain vertices to have palettes of size less than five assigned to them. In this dissertation, we explore both of these questions and answer them in the affirmative for various classes of graphs.
We also provide a catalog of small configurations with palettes of different prescribed sizes and determine whether or not they can always be colored from palettes of such sizes. These small configurations can be useful in reducing certain planar graphs to obtain more information about their structure.
Additionally, we look at the newer notion of sum-list-coloring where the sum choice number is the parameter of interest. In sum-list-coloring, we seek to minimize the sum of varying sizes of palettes of colors assigned the vertices of a graph. We compute the sum choice number for all graphs on at most five vertices, present some general results about sum-list-coloring, and determine the sum choice number for certain graphs made up of cycles.
DOI
https://doi.org/10.31274/etd-180810-1195
Copyright Owner
Michelle Anne Lastrina
Copyright Date
2012
Language
en
Date Available
2012-10-31
File Format
application/pdf
File Size
127 pages
Recommended Citation
Lastrina, Michelle Anne, "List-coloring and sum-list-coloring problems on graphs" (2012). Graduate Theses and Dissertations. 12376.
https://lib.dr.iastate.edu/etd/12376
