Colored squares

While working on a new Wikipedia entry for angular resolution, I ran across a curious connection between coloring, degeneracy, degree, and graph squaring.

The square of a graph \( G \) is the graph on the same vertex set, with two vertices connected by an edge in the square whenever they have distance at most two in \( G. \) The original paper on angular resolution by Formann et al showed that the chromatic number of the square is closely related to the angular resolution: if the square can be colored with \( k \) colors, then place the vertices of \( G \) in a circular layout, with each vertex near the corner of a regular \( k \)-gon that corresponds to its color. The resulting layout will have angular resolution around \( \pi/k, \) although it will likely be bad in other ways — for instance, pairs of edges that connect vertices of the same color will be drawn very close to each other. Square-coloring has also been used for frequency assignment in wireless networks: one wants nodes two hops from each other to have different frequencies so that their common neighbor can hear both of them without interference.

In an unpublished paper from 1977 by Wegner, cited in a more recent survey by Kramer and Kramer, he conjectures that the squares of planar graphs have chromatic number at most \( \max(\Delta+5, 3\Delta/2+1) \) where \( \Delta \) is the maximum degree of the graph. Formann et al rediscovered the problem independently and and showed that the chromatic number of the square is at most \( 13\Delta/7+O(\Delta^2/3); \) a better bound of \( 5\Delta/3+O(1) \) proven by Molloy and Salavatipour is mentioned by Kramer and Kramer. Because of these bounds, planar graphs may be drawn (nonplanarly) with angular resolution inversely proportional to \( \Delta, \) whereas nonplanar graphs may need angular resolution closer to \( 1/\Delta^2. \)

The argument of Formann et al uses careful analysis of the numbers of vertices of degrees near the maximum, based on the Euler characteristic of the graph. But if you just want a bound that's linear in \( \Delta, \) it can be done much more easily based on the degeneracy of the graph, a number \( d \) such that every subgraph has a vertex of degree at most \( d. \) Planar graphs have degeneracy at most five, and the chromatic number of any graph is at most one more than its degeneracy. It turns out that, for any graph \( G \) with degeneracy \( d \) and maximum degree \( \Delta, \) the degeneracy of \( G^2 \) is at most \( 2d\Delta. \) For, if the vertices of \( G \) are placed into a sequence so that each vertex has at most \( d \) later neighbors in the sequence (an equivalent definition of degeneracy) then each path of length at most two from a vertex \( v \) to a later vertex must have at least one forward-going edge. There are at most \( d\Delta \) paths that start with a forward edge and at most \( \Delta d \) paths that end with a forward edge, and adding them together gives the bound on the number of later neighbors in \( G^2. \)

This bound shows only that the chromatic number of the square of a planar graph is at most \( 10\Delta, \) very far from Wegner's conjecture, but it generalizes to any family of graphs in which all subgraphs are sparse and shows that they all have drawings with angular resolution linear in their degree.

Unrelatedly, I was inspired by the visit of Mike Goodrich's academic sibling Marina Blanton (who is giving a colloquium here tomorrow on privacy-preserving computations for biometrics) to add another article on their common advisor, Mike Atallah. And while I'm at it, even more unrelatedly, an earlier algorithms researcher: Selmer M. Johnson.

---

Comments: