Ursidae: The Undergraduate Research Journal at the University of Northern Colorado
Faculty Sponsor
Oscar Levin
Abstract
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.
Recommended Citation
Myrant, Cat
(2014)
"Face-wise Chromatic Number,"
Ursidae: The Undergraduate Research Journal at the University of Northern Colorado: Vol. 4:
No.
2, Article 10.
Available at:
https://digscholarship.unco.edu/urj/vol4/iss2/10