List-coloring the square of a subcubic graph

✍ Scribed by Daniel W. Cranston; Seog-Jin Kim

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 266 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20273

✦ Synopsis

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