## HMC Senior Theses

#### Title

Extending List Colorings of Planar Graphs

2011

#### Document Type

Open Access Senior Thesis

#### Degree Name

Bachelor of Science

Mathematics

Kimberly Kindred

#### Reader 2

Susan E. Martonosi

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\$.

COinS