Date of Award
5-2011
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
First Thesis Advisor
Kimberly Kindred
Second Thesis Advisor
Susan E. Martonosi
Rights Information
Sarah Loeb
Terms of Use & License Information
Abstract
In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.
Recommended Citation
Loeb, Sarah, "Extending List Colorings of Planar Graphs" (2011). HMC Senior Theses. Paper 6.
http://scholarship.claremont.edu/hmc_theses/6