Geodesic
2-distance 4-colorability of planar subcubic graphs with girth at least 22
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 141-151.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: planar graph, subcubic graph, 2-distance coloring 
@article{DMGT_2012_32_1_a11,
     author = {Borodin, Oleg and Ivanova, Anna},
     title = {2-distance 4-colorability of planar subcubic graphs with girth at least 22},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {141--151},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a11/}
}
TY  - JOUR
AU  - Borodin, Oleg
AU  - Ivanova, Anna
TI  - 2-distance 4-colorability of planar subcubic graphs with girth at least 22
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 141
EP  - 151
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a11/
LA  - en
ID  - DMGT_2012_32_1_a11
ER  - 
%0 Journal Article
%A Borodin, Oleg
%A Ivanova, Anna
%T 2-distance 4-colorability of planar subcubic graphs with girth at least 22
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 141-151
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a11/
%G en
%F DMGT_2012_32_1_a11
Borodin, Oleg; Ivanova, Anna. 2-distance 4-colorability of planar subcubic graphs with girth at least 22. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 1, pp. 141-151. http://geodesic.mathdoc.fr/item/DMGT_2012_32_1_a11/

[1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, in: Combinatorics, Proc. SODA'00 (SIAM, 2000) 654-662.

[2] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662, doi: 10.1137/S0895480100367950.

[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).

[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).

[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).

[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.

[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.

[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).

[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).

[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).

[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).

[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.

[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.

[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.

[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).

[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).

[17] T. Jensen and B. Toft, Graph Coloring Problems (New York: John Willey Sons, 1995).

[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.

[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.

[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.

[21] G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, University of Dortmund, Germany, 1977).