Abstract
An incidence of a graph G is a pair (v,e) where v is a vertex of G and e an edge incident to v. Two incidences (v,e) and (w,f) are adjacent whenever v = w, or e = f, or vw = e or f. The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980–1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number i g (G) of a graph G is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on G.
Andres proved that \(i_g(G) \le 2\varDelta(G) + 4k - 2\) for every k-degenerate graph G. We show in this paper that \(i_g(G) \le \lfloor\frac{3\varDelta(G) - a(G)}{2}\rfloor + 8a(G) - 2\) for every graph G, where a(G) stands for the arboricity of G, thus improving the bound given by Andres since a(G) ≤ k for every k-degenerate graph G. Since there exists graphs with \(i_g(G) \ge \lceil\frac{3\varDelta(G)}{2}\rceil\), the multiplicative constant of our bound is best possible.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andres, S.: The incidence game chromatic number. Discrete Appl. Math. 157, 1980–1987 (2009)
Bartnicki, T., Grytczuk, J., Kierstead, H.A., Zhu, X.: The map coloring game. Amer. Math. Monthly (November 2007)
Bodlaender, H.: On the complexity of some coloring games. Int. J. Found. Comput. Sci. 2, 133–147 (1991)
Brualdi, R., Massey, J.: Incidence and strong edge colorings of graphs. Discrete Math. 122, 51–58 (1993)
Charpentier, C., Sopena, E.: The incidence game chromatic number of forests (preprint, 2013)
Dinski, T., Zhu, X.: Game chromatic number of graphs. Discrete Math. 196, 109–115 (1999)
Gardner, M.: Mathematical game. Scientific American 23 (1981)
Hosseini Dolama, M., Sopena, E.: On the maximum average degree and the incidence chromatic number of a graph. Discrete Math. and Theoret. Comput. Sci. 7(1), 203–216 (2005)
Hosseini Dolama, M., Sopena, E., Zhu, X.: Incidence coloring of k-degenerated graphs. Discrete Math. 283, 121–128 (2004)
Kierstead, H.: A simple competitive graph coloring algorithm. J. Combin. Theory Ser. B 78(1), 57–68 (2000)
Kierstead, H., Trotter, W.: Planar graph coloring with an uncooperative partner. J. Graph Theory 18, 569–584 (1994)
Kim, J.: The incidence game chromatic number of paths and subgraphs of wheels. Discrete Appl. Math. 159, 683–694 (2011)
Maydansky, M.: The incidence coloring conjecture for graphs of maximum degree three. Discrete Math. 292, 131–141 (2005)
Sopena, E.: http://www.labri.fr/perso/sopena/TheIncidenceColoringPage
Wang, S., Chen, D., Pang, S.: The incidence coloring number of Halin graphs and outerplanar graphs. Discrete Math. 256, 397–405 (2002)
Zhu, X.: The game coloring number of planar graphs. J. Combin. Theory Ser. B 75(2), 245–258 (1999)
Zhu, X.: Refined activation strategy for the marking game. J. Combin. Theory Ser. B 98(1), 1–18 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Charpentier, C., Sopena, É. (2013). Incidence Coloring Game and Arboricity of Graphs. In: Lecroq, T., Mouchard, L. (eds) Combinatorial Algorithms. IWOCA 2013. Lecture Notes in Computer Science, vol 8288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45278-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-45278-9_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45277-2
Online ISBN: 978-3-642-45278-9
eBook Packages: Computer ScienceComputer Science (R0)