An improved bound on 2-distance coloring plane graphs with girth 5
Tóm tắt
A vertex coloring is called
$$2$$
-distance if any two vertices at distance at most
$$2$$
from each other get different colors. The minimum number of colors in 2-distance colorings of
$$G$$
is its 2-distance chromatic number, denoted by
$$\chi _2(G)$$
. Let
$$G$$
be a plane graph with girth at least
$$5$$
. In this paper, we prove that
$$\chi _2(G)\le \Delta +8$$
for arbitrary
$$\Delta (G)$$
, which partially improves some known results.
Tài liệu tham khảo
Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan Ltd. Press, New York
Borodin OV, Broersma H, Glebov A, van den Heuvel J (2002) Stars and bunches in planar graphs. General planar graphs and colourings. CDAM Researches Report Part II
Borodin OV, Ivanova AO (2009) 2-Distance \(\Delta +2\)-coloring of planar graphs with girth six and \(\Delta \ge 18\). Discret Math 309:6496–6502
Borodin OV, Ivanova AO, Neustroeva TK (2004) 2-Distance coloring of sparse plane graphs. Sib Èlektron Math Izv 1:76–90 (in Russian)
Borodin OV, Glebov AN, Ivanova AO, Neustroeva TK, Tashkinov VA (2004) Sufficient conditions for the 2-distance \(\Delta +1\)-colorability of plane graphs. Sib lektron Math Izv 1:129–141 (in Russian)
Bu Y, Zhu X (2012) An optimal square coloring of planar graphs. J Comb Optim 24:580–592
Bu Y, Yan X (2014) List 2-distance coloring of planar graphs. J Comb Optim doi:10.1007/s10878-013-9700-2
Charpentier C, Montassier M, Raspaud A (2013) L(p, q)-labeling of sparse graphs. J Comb Optim 25:646–660
Dvořàk Z, Kràl D, Nejedlỳ P, Škrekovski R (2008) Coloring squares of planar graphs with girth six. Eur J Comb 29:838–849
Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory Ser B 94:189–213
van den Heuvel J, McGuinness S (2003) Coloring of the square of planar graph. J Graph Theory 42:110–124
Wang W, Lih K (2003) Labeling planar graphs with conditions on girth and distance two. SIAM J Discret Math 17(2):264–275
Wegner G (1977) Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany