Face-wise Chromatic Number
Cat Myrant, Faculty Mentor Oscar Levin · Scholarship & Creative Works - Digital UNC a service of University Libraries (University of Northern Colorado) · 2014
The chromatic number is a well-studied graph invariant. This is the smallest number of colors necessary to color all the vertices such that no two vertices adjacent to the same edge are the same color. It has a myriad of applications from scheduling problems to cartography. Here we consider what happens when we color vertices with respect to faces instead of edges. That is, two vertices adjacent to the same face must not be the same color. We call this invariant the face-wise chromatic number (fwcn). We will see how to compute the fwcn for a variety of graphs and look at connections between the fwcn and the classical chromatic number.