PDF

Discussiones Mathematicae Graph Theory 32(1) (2012) 141-151
DOI: https://doi.org/10.7151/dmgt.1592

2-distance 4-colorability of Planar Subcubic Graphs with Girth at least 22

Oleg V. Borodin Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, and Novosibirsk State University, Novosibirsk, 630090, Russia

Anna O. Ivanova Institute of Mathematics at Yakutsk State University and North-Eastern Federal University, Yakutsk, 677891, Russia

Abstract

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

2010 Mathematics Subject Classification: 05C15.

References

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

Received 23 November 2010
Revised 24 March 2011
Accepted 26 March 2011