Combinatorics-Coloring Squares of Planar Graphs

Speaker: Dan Cranston, Virginia Commonwealth University
Date and time: Tuesday, March 6, 1-2pm
Place: Rome 771
Title: Coloring Squares of Planar Graphs

Abstract:  The square, G^2, of a graph G is formed from G by adding an edge joining each pair of vertices at distance 2 in G. If G has maximum degree k, then G^2 can have maximum degree as big as k^2 and the chromatic number, \chi(G^2), of G^2 can be as big as k^2+1. Two examples that achieve equality are the 5-cycle and the Petersen graph. In general these bounds cannot be improved much. For example, if G is the incidence graph of a projective plane and G has maximum degree k, then G^2 has maximum degree k^2 and \chi(G^2) \approx k^2-k. However, for planar graphs, we can do much better.

It is easy to show that if G is a planar graph with maximum degree k, then \chi(G^2) \le 9k; in fact, this bound can be greatly improved. However, constructions show that we cannot improve it beyond 3k/2+1.  Further, every graph G with maximum degree k trivially satisfies \chi(G^2)\ge k+1. We survey various classes of planar graphs for which this trivial lower bound holds with equality or nearly holds with equality. More precisely, we seek a graph class \mathcal{H} and a constant C such that every graph G\in \mathcal{H} with maximum degree k satisfies \chi(G^2) \le k+C. Our main result is that if \mathcal{H} is defined by forbidding certain lengths of cycles, then \mathcal{H} has this property if and only if we forbid either (i) 4-cycles or (ii) all even cycles of length at least 6.

This is joint work with Ilkyoo Choi.