The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1592,
author = {Oleg V. Borodin and Anna O. Ivanova},
title = {2-distance 4-colorability of planar subcubic graphs with girth at least 22},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {141-151},
zbl = {1255.05075},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1592}
}
Oleg V. Borodin; Anna O. Ivanova. 2-distance 4-colorability of planar subcubic graphs with girth at least 22. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 141-151. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1592/
[000] [1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, in: Combinatorics, Proc. SODA'00 (SIAM, 2000) 654-662. | Zbl 0965.05042
[001] [2] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662, doi: 10.1137/S0895480100367950. | Zbl 1029.05047
[002] [3] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. van den Heuvel, The minimum degree and chromatic number of the square of a planar graph, Diskretn. Anal. Issled. Oper., 8 no. 4 (2001) 9-33 (in Russian). | Zbl 1012.05074
[003] [4] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. van den Heuvel, The structure of plane triangulations in terms of stars and bunches, Diskretn. Anal. Issled. Oper. 8 no. 2 (2001) 15-39 (in Russian). | Zbl 0977.05036
[004] [5] O.V. Borodin, A.N. Glebov, A.O. Ivanova, T.K. Neustroeva and V.A. Tashkinov, Sufficient conditions for the 2-distance Δ+1-colorability of plane graphs, Sib. Elektron. Mat. Izv. 1 (2004) 129-141 (in Russian). | Zbl 1076.05032
[005] [6] O.V. Borodin and A.O. Ivanova, 2-distance (Δ+2)-coloring of planar graphs with girth six and Δ≥ 18, Discrete Math. 309 (2009) 6496-6502, doi: 10.1016/j.disc.2009.06.029. | Zbl 1184.05040
[006] [7] O.V. Borodin and A.O. Ivanova, List 2-distance (Δ+2)-coloring of planar graphs with girth six, Europ. J. Combin. 30 (2009) 1257-1262, doi: 10.1016/j.ejc.2008.12.019. | Zbl 1190.05055
[007] [8] O.V. Borodin and A.O. Ivanova, 2-distance 4-coloring of planar subcubic graphs, Diskretn. Anal. Issled. Oper. 18 no. 2 (2011) 18-28 (in Russian).
[008] [9] O.V. Borodin, A.O. Ivanova and T.K. Neustroeva, 2-distance coloring of sparse plane graphs, Sib. Elektron. Mat. Izv. 1 (2004) 76-90 (in Russian). | Zbl 1077.05040
[009] [10] O.V. Borodin, A.O. Ivanova and T.K. Neustroeva, Sufficient conditions for 2-distance (Δ+1)-colorability of planar graphs of girth 6, Diskretn. Anal. Issled. Oper. 12 no.3 (2005) 32-47 (in Russian). | Zbl 1249.05113
[010] [11] O.V. Borodin, A.O. Ivanova and T.K. Neustroeva, Sufficient conditions for the minimum 2-distance colorability of planar graphs with girth 6, Sib. Elektron. Mat. Izv. 3 (2006) 441-450 (in Russian). | Zbl 1119.05039
[011] [12] Z. Dvořák, D. Kràl, P. Nejedlỳ and R. Škrekovski, Coloring squares of planar graphs with girth six, European J. Combin. 29 (2008) 838-849, doi: 10.1016/j.ejc.2007.11.005. | Zbl 1143.05027
[012] [13] Z. Dvořák, R. Škrekovski and M. Tancer, List-coloring squares of sparse subcubic graphs, SIAM J. Discrete Math. 22 (2008) 139-159, doi: 10.1137/050634049. | Zbl 1159.05018
[013] [14] F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353-3563, doi: 10.1016/j.disc.2007.12.100. | Zbl 1213.05084
[014] [15] A.O. Ivanova, List 2-distance (Δ+1)-coloring of planar graphs with girth at least 7, Diskretn. Anal. Issled. Oper. 17 no.5 (2010) 22-36 (in Russian). | Zbl 1249.05118
[015] [16] A.O. Ivanova and A.S. Solov'eva, 2-Distance (Δ +2)-coloring of sparse planar graphs with Δ=3, Mathematical Notes of Yakutsk University 16 no. 2 (2009) 32-41 (in Russian).
[016] [17] T. Jensen and B. Toft, Graph Coloring Problems (New York: John Willey & Sons, 1995).
[017] [18] M. Molloy and M.R. Salavatipour, Frequency channel assignment on planar networks, in: LNCS, ed(s), R.H. Möhring and R. Raman (Springer, 2002) 736-747. | Zbl 1040.90034
[018] [19] M. Molloy and M.R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory (B) 94 (2005) 189-213, doi: 10.1016/j.jctb.2004.12.005. | Zbl 1071.05036
[019] [20] M. Montassier and A. Raspaud, A note on 2-facial coloring of plane graphs, Inform. Process. Lett. 98 (2006) 235-241, doi: 10.1016/j.ipl.2006.02.013. | Zbl 1178.05042
[020] [21] G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, University of Dortmund, Germany, 1977).