×

zbMATH — the first resource for mathematics

The square of a planar cubic graph is 7-colorable. (English) Zbl 1375.05110
Summary: We prove the conjecture made by G. Wegner [“Graphs with given diameter and a coloring problem”, Preprint, University of Dortmund] that the square of every planar, cubic graph is 7-colorable. Here, 7 cannot be replaced by 6.

MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bu, Y.; Zhu, X., An optimal square coloring of planar graphs, J. Comb. Optim., 24, 580-592, (2012) · Zbl 1261.05022
[2] Cranston, D. W.; Jaeger, B., List-coloring the squares of planar graphs without 4-cycles and 5-cycles, (13 May 2015)
[3] Dvořák, Z.; Král, D.; Nejedlý, P.; Škrekovski, R., Coloring squares of planar graphs with girth six, European J. Combin., 29, 838-849, (2008) · Zbl 1143.05027
[4] Gionfriddo, M., A short survey of some generalized colorings of graphs, Ars Combin., 30, 275-284, (1986)
[5] Hartke, S. G.; Jahanbekam, S.; Thomas, B., The chromatic number of the square of subcubic planar graphs, (21 May 2016)
[6] Jensen, T.; Toft, B., Graph coloring problems, (1995), John Wiley New York · Zbl 0855.05054
[7] Kim, S.-J.; Park, B., Coloring the squares of graphs whose maximum average degrees are less than 4, (14 Jun. 2015)
[8] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Časopis. Slovensk. Akad. Vied., 5, 101-113, (1955)
[9] Mohar, B.; Thomassen, C., Graphs on surfaces, (2001), Johns Hopkins University Press Baltimore · Zbl 0979.05002
[10] Molloy, M.; Salavatipour, M. R., A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B, 94, 189-213, (2005) · Zbl 1071.05036
[11] G. Wegner, Graphs with given diameter and a coloring problem, preprint, University of Dortmund, 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.