Discrete Mathematics Seminar

Dan Cranston telling us about: Equitably Coloring Planar and Outerplanar Graphs (abstract below). The talk will be on zoom at this link. We will have a watch party in Carver 401 (the projector has been repaired), and you are also welcome to join via zoom.

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.