Graduation Year
2011
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Kimberly Kindred
Reader 2
Susan E. Martonosi
Terms of Use & License Information
Rights Information
Sarah Loeb
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. 6.
https://scholarship.claremont.edu/hmc_theses/6
