Download PDF - 2-distance 4-colorability of planar subcubic graphs with girth at least 22All rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Authors 1, 2

Affiliations

  1. Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, and Novosibirsk State University, Novosibirsk, 630090, Russia
  2. 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

ENG
planar graph, subcubic graph, 2-distance coloring

Bibliography

  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).
Discussiones Mathematicae Graph Theory
2012/32/1
Export to PBN, Opens in new tab
Pages:
141-151
Main language of publication
English
Received
2010-11-23
Accepted
2011-03-24
Published
2012

DOI: 10.7151/dmgt.1592

Exact and natural sciences