Coloring squares of planar graphs 03/06/2018

Speaker: Dan Cranston, VCU
Date and time: Tuesday, March 6, 1-2pm
Place: Rome 771
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.