# 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

## Access Full Article

top## Abstract

top## How to cite

topOleg 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] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, in: Combinatorics, Proc. SODA'00 (SIAM, 2000) 654-662. Zbl0965.05042
- [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] 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] 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] 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] 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] 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] 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). Zbl1077.05040
- [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] 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] 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] 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] 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] 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] 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. Zbl1040.90034
- [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] 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] G. Wegner, Graphs with Given Diameter and a Coloring Problem (Technical Report, University of Dortmund, Germany, 1977).

## Citations in EuDML Documents

top## NotesEmbed ?

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