×

List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six. (English) Zbl 1190.05055

Suppose each vertex of a graph \(G\) is assigned a list of at least \(k\) admissible colors; then \(G\) is said to be list 2-distance \(k\)-colorable if, for any such collection of lists, it is possible to give each vertex one of its admissible colors in such a way that any two vertices at distance at most two apart receive different colors. The authors show that any planar graph with girth at least 6 and maximum degree \(D\) at least 36 is list 2-distance \((D+2)\)-colorable.

MSC:

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany, 1977; G. Wegner, Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany, 1977
[2] Agnarsson, G.; Halldorsson, M. M., Coloring powers of planar graphs, (Proc. SODA’00 (2000), SIAM press), 654-662 · Zbl 0965.05042
[3] Agnarsson, G.; Halldorsson, M. M., Coloring powers of planar graphs, SIAM J. Discrete Math., 16, 4, 651-662 (2003) · Zbl 1029.05047
[4] Borodin, O. V.; Broersma, H. J.; Glebov, A.; van den Heuvel, J., The structure of plane triangulations in terms of stars and bunches, Discrete Anal. Oper. Res., 8, 2, 15-39 (2001), (in Russian) · Zbl 0977.05036
[5] Borodin, O. V.; Broersma, H. J.; Glebov, A.; van den Heuvel, J., The minimum degree and chromatic number of the square of planar graph, Discrete Anal. Oper. Res., 8, 4, 9-33 (2001), (in Russian) · Zbl 1012.05074
[6] Molloy, M.; Salavatipour, M. R., Frequency channel assignment on planar networks, (Mohring, R. H.; Raman, R., LNCS, vol. 2461 (2002), Springer), 736-747 · Zbl 1040.90034
[7] 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
[8] Havet, F.; van den Heuvel, J.; McDiarmid, C.; Reed, B., List colouring squares of planar graphs, Eurocomb07, Electron. Notes Discrete Math., 29, 515-519 (2007) · Zbl 1341.05073
[9] Borodin, O. V.; Ivanova, A. O.; Neustroeva, T. K., 2-distance coloring of sparse plane graphs, Siberian Electron. Math. Reports, 1, 76-90 (2004), (in Russian). http://semr.math.nsc.ru · Zbl 1077.05040
[10] Borodin, O. V.; Glebov, A. N.; Ivanova, A. O.; Neustroeva, T. K.; Tashkinov, V. A., Sufficient conditions for the 2-distance \(\Delta + 1\)-colorability of plane graphs, Siberian Electron. Math. Reports, 1, 129-141 (2004), (in Russian). http://semr.math.nsc.ru · Zbl 1076.05032
[11] Borodin, O. V.; Ivanova, A. O.; Neustroeva, T. K., List 2-distance \((\Delta + 1)\)-coloring of planar graphs with given girth, Discrete Anal. Oper. Res., 14, 3, 13-30 (2007), (in Russian) · Zbl 1249.05114
[12] Borodin, O. V.; Ivanova, A. O.; Neustroeva, T. K., Sufficient conditions for 2-distance \(( \Delta + 1)\)-colorability of planar graphs of girth 6, Discrete Anal. Oper. Res., 12, 3, 32-47 (2005), (in Russian) · Zbl 1249.05113
[13] Borodin, O. V.; Ivanova, A. O.; Neustroeva, T. K., Sufficient conditions for the minimum 2-distance colorability of planar graphs with girth 6, Siberian Electron. Math. Reports, 3, 441-450 (2006), (in Russian). http://semr.math.nsc.ru · Zbl 1119.05039
[14] Dvořàk, Z.; Kràl, D.; Nejedlỳ, P.; Škrekovski, R., Coloring squares of planar graphs with girth six, European J. Combin., 29, 4, 838-849 (2008) · Zbl 1143.05027
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.