zbMATH — the first resource for mathematics

Choosability of the square of planar subcubic graphs with large girth. (English) Zbl 1213.05084
Summary: We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] O.V. Borodin, Criterion of chromaticity of a degree prescription, in: Abstracts of IV All-Union Conf. on Theoretical Cybernetics (Novosibirsk), 1977, pp. 127-128 (in Russian)
[2] D.W. Cranston, S.-J. Kim, List-coloring the square of a subcubic graph, manuscript, 2006 · Zbl 1172.05023
[3] Z. Dvořák, R. Škrekovski, M. Tancer, List-colouring squares of sparse subcubic graphs, IMFM Preprint PS-985, 2005
[4] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), in: Congress. Numer., XXVI, Winnipeg, Man., Utilitas Math., 1980, pp. 125-157
[5] Fleischner, H.; Stiebitz, M., A solution to a colouring problem of P. Erdös, Discrete math., 101, 39-48, (1992) · Zbl 0759.05037
[6] Kostochka, A.V.; Woodall, D.R., Choosability conjectures and multicircuits, Discrete math., 240, 1-3, 123-143, (2001) · Zbl 0989.05041
[7] Montassier, M.; Raspaud, A., A note on 2-facial coloring of plane graphs, Inform. process. lett., 98, 6, 211-266, (2006)
[8] C. Thomassen, The square of a planar cubic graph is 7-colorable, manuscript, 2006
[9] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany, 1977
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.