- Sponsor
- Department of Mathematics
- Speaker
- Daniel Cranston (College of William and Mary)
- Contact
- Abhishek Dhawan
- adhawan2@illinois.edu
- Views
- 3
Speaker: Daniel Cranston (College of William and Mary)
Title: Equitably Coloring Planar and Outerplanar Graphs
Abstract: A proper s-coloring of an n-vertex graph is \emph{equitable} if every color class has size floor(n/s) or ceiling(n/s). A necessary condition to have an equitable s-coloring is that every vertex appears in an independent set of size at least floor(n/s). Various authors showed that when G is a tree and s >= 3 this obvious necessary condition is also sufficient. Kierstead, Kostochka, and Xiang asked whether this result holds more generally for all outerplanar graphs. We show that the answer is No when s = 3, but that the answer is Yes when s >= 6. The case s \in {4,5} remains open. We also prove an analogous result for planar graphs, with a necessary and sufficient hypothesis (when s >= 40). This is joint work with Reem Mahmoud.