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

Oleg V. Borodin; Anna O. Ivanova

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 141-151
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Oleg V. Borodin, and Anna O. Ivanova. "2-distance 4-colorability of planar subcubic graphs with girth at least 22." Discussiones Mathematicae Graph Theory 32.1 (2012): 141-151. <http://eudml.org/doc/270944>.

@article{OlegV2012,
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.},
author = {Oleg V. Borodin, Anna O. Ivanova},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; subcubic graph; 2-distance coloring},
language = {eng},
number = {1},
pages = {141-151},
title = {2-distance 4-colorability of planar subcubic graphs with girth at least 22},
url = {http://eudml.org/doc/270944},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Oleg V. Borodin
AU - Anna O. Ivanova
TI - 2-distance 4-colorability of planar subcubic graphs with girth at least 22
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 141
EP - 151
AB - 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.
LA - eng
KW - planar graph; subcubic graph; 2-distance coloring
UR - http://eudml.org/doc/270944
ER -

References

top
  1. [1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, in: Combinatorics, Proc. SODA'00 (SIAM, 2000) 654-662. Zbl0965.05042
  2. [2] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662, doi: 10.1137/S0895480100367950. Zbl1029.05047
  3. [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). Zbl1012.05074
  4. [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). Zbl0977.05036
  5. [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). Zbl1076.05032
  6. [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. Zbl1184.05040
  7. [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. Zbl1190.05055
  8. [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. [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). Zbl1077.05040
  10. [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). Zbl1249.05113
  11. [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). Zbl1119.05039
  12. [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. Zbl1143.05027
  13. [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. Zbl1159.05018
  14. [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. Zbl1213.05084
  15. [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). Zbl1249.05118
  16. [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. [17] T. Jensen and B. Toft, Graph Coloring Problems (New York: John Willey & Sons, 1995). 
  18. [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. Zbl1040.90034
  19. [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. Zbl1071.05036
  20. [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. Zbl1178.05042
  21. [21] G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, University of Dortmund, Germany, 1977). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.