Ursidae: The Undergraduate Research Journal at the University of Northern Colorado


Cat Myrant

Faculty Sponsor

Oscar Levin


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.