zbMATH — the first resource for mathematics

List-coloring the square of a subcubic graph. (English) Zbl 1172.05023
Summary: 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 \(\Delta(G)=3\) satisfies \(\chi(G^2)\leq7\). Kostochka and Woodall conjectured that for every graph, the list-chromatic number of \(G^2\) equals the chromatic number of \(G^2\), that is, \(\chi_l(G^2)= \chi(G^2)\) for all \(G\). If true, this conjecture (together with Thomassen’s result) implies that every planar graph \(G\) with \(\Delta(G)=3\) satisfies \(\chi_l(G^2)\leq7\). We prove that every connected graph (not necessarily planar) with \(\Delta(G)=3\) other than the Petersen graph satisfies \(\chi_l(G^2)\leq 8\) (and this is best possible). In addition, we show that if \(G\) is a planar graph with \(\Delta(G)=3\) and girth \(g(G)\geq7\), then \(\chi_l(G^2)\leq7\). Dvořák, Škrekovski, and Tancer showed that if \(G\) is a planar graph with \(\Delta(G)=3\) and girth \(g(G)\geq10\), then \(\chi_l(G^2)\geq 6\). We improve the girth bound to show that if \(G\) is a planar graph with \(\Delta(G)=3\) and \(g(G)\geq 9\), then \(\chi_l(G^2)\leq 6\). All of our proofs can be easily translated into linear-time coloring algorithms.

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
Full Text: DOI arXiv
[1] Borodin, (Russian) Sib Elektron Mat Izv 1 pp 129– (2004)
[2] Brown, Canad Math Bull 9 pp 281– (1966) · Zbl 0178.27302 · doi:10.4153/CMB-1966-036-2
[3] , and , List-coloring squares of sparse subcubic graphs, submitted for publication.
[4] , , and , Coloring squares of planar graphs with no short cycles, submitted for publication.
[5] , and , Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, California, 1979, Congressus Numeratium, 26 ( 1980), 125–157.
[6] , and , Maximum degree in graphs of diameter 2, Networks 10 ( 1980), 87–90. · Zbl 0427.05042
[7] Fleischner, Discrete Math 101 pp 39– (1992)
[8] Choosability of the square of planar subcubic graphs with large girth, Technical Report, INRIA, 2006.
[9] , , and , List colouring squares of planar graphs, Eurocomb’07, September 2007, Seville University.
[10] Hoffman, IBM Journal of Research and Development 4 pp 497– (1960)
[11] Huxley, Invent Math 15 pp 164– (1972)
[12] Juvan, Combinatorics, Probability and Computing 7 pp 181– (1998)
[13] Kostochka, Discrete Math 240 pp 123– (2001)
[14] and , Moore graphs and beyond: A survey of the degree/diameter problem., www.combinatorics.org/Surveys/ds14.pdf ( 2005), p. 12.
[15] Molloy, J Combin Theory Ser B 94 pp 189– (2005)
[16] Wang, SIAM J Discrete Math 17 pp 264– (2003)
[17] The square of a planar cubic graph is 7-colorable, manuscript. · Zbl 1375.05110
[18] Graphs with given diameter and a coloring problem, preprint, University of Dortmund, Dortmund, Germany, 1977.
[19] Introduction to graph theory, 2nd edition. Prentice Hall, Old Tappan, NJ, 2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.