×

On the game coloring index of \(F^+\)-decomposable graphs. (English) Zbl 1377.05114

Summary: The game coloring index \(\text{col}_g^\prime(G)\) of a graph \(G\) is the score of the edge marking game (the edge-coloring version of the marking game) on \(G\) when the two players use their best strategy. The game coloring index is at most \(\Delta + 2\) for the class of forests of maximum degree \(\Delta\), denoted \(\mathcal{F}_\Delta\). We prove that \(\text{col}_g^\prime(G) \leq \Delta(G) + 3 a - 1\) for every graph \(G\) of arboricity \(a\), i.e. every graph decomposable into \(a\) forests and we introduce a generalized decomposition of the well-known \((a, d)\)- and \(F(a, d)\)-decompositions to improve this result. In particular, we improve bounds for some planar graphs.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A05 2-person games
Full Text: DOI

References:

[1] Andres, S. D., The game chromatic index of forests of maximum degree \(\triangle \geq 5\), Discrete Math., 154, 1317-1323 (2006) · Zbl 1091.05023
[4] Borodin, O.; Ivanova, A.; Kostochka, A.; Sheik, N., Decompositions of quadrangle-free planar graphs, Discuss. Math. Graph Theory, 29, 87-99 (2009) · Zbl 1181.05034
[6] Charpentier, C.; Sopena, É., The incidence game chromatic number of \((a, d)\)-partitionable graphs, J. Discrete Algorithms, 31, 14-25 (2015) · Zbl 1325.05074
[7] Erdös, P. L.; Faigle, U.; Hochstättler, W.; Kern, W., Note on the game chromatic index of trees, Theoret. Comput. Sci., 313, 371-376 (2004) · Zbl 1066.91015
[8] Faigle, U.; Kern, W.; Kierstead, H. A.; Trotter, W. T., On the game chromatic number of some classes of graphs, Ars Combin., 35, 143-150 (1993) · Zbl 0796.90082
[9] Gardner, M., Mathematical Games (1981)
[10] Gonçalves, D., Covering planar graphs with forests, one having bounded maximum degree, J. Combin. Theory Ser. B, 99, 314-322 (2009) · Zbl 1205.05179
[11] Lam, P. C.B.; Shiu, W. C.; Xu, B., Edge game coloring of graphs, Graph Theory Notes, 37, 17-19 (1999)
[12] Montassier, M.; Ossona de Mendez, P.; Raspaud, A.; Zhu, X., Decomposing a graph into forests, J. Combin. Theory Ser. B, 102, 38-52 (2012) · Zbl 1237.05167
[13] Nash-Williams, C., Decomposition of finite graphs into forests, J. Lond. Math. Soc., s1-39, 1, 12 (1964) · Zbl 0119.38805
[14] Wang, Y.; Zhang, Q., Decomposing a planar graph with girth at least \(8\) into a forest and a matching, Discrete Math., 311, 844-849 (2011) · Zbl 1223.05047
[15] Zhu, X., The game coloring number of planar graphs, J. Combin. Theory Ser. B, 75, 245-258 (1999) · Zbl 0933.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.