List‐coloring the square of a subcubic graph

Abstract

Abstract The square G 2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ( G ) = 3 satisfies χ( G 2 ) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G 2 equals the chromatic number of G 2 , that is, χ l ( G 2 ) = χ( G 2 ) for all G . If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ( G ) = 3 satisfies χ l ( G 2 ) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ( G ) = 3 other than the Petersen graph satisfies χ l ( G 2 ) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ( G ) = 3 and girth g ( G ) ≥ 7, then χ l ( G 2 ) ≤ 7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ( G ) = 3 and girth g ( G ) ≥ 10, then χ l ( G 2 ) ≤6. We improve the girth bound to show that if G is a planar graph with Δ( G ) = 3 and g ( G ) ≥ 9, then χ l ( G 2 ) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008