Equality perfect graphs and digraphs. (English) Zbl 1445.05068
Summary: In the graph colouring game introduced by H. L. Bodlaender [Int. J. Found. Comput. Sci. 2, No. 2, 133–147 (1991; Zbl 0753.05061)], two players, Alice and Bob, alternately colour uncoloured vertices of a given graph \(G\) with one of \(k\) colours so that adjacent vertices receive different colours. Alice wins if every vertex is coloured at the end. The game chromatic number of \(G\) is the smallest \(k\) such that Alice has a winning strategy.
In Bodlaender’s original game, Alice begins. We also consider variants of this game where Bob begins or skipping turns is allowed [the author, Math. Methods Oper. Res. 69, No. 2, 235–250 (2009; Zbl 1161.91331)] and their generalizations to digraphs [the author, Discrete Math. 309, No. 11, 3564–3579 (2009; Zbl 1225.05105)]. By means of forbidden induced subgraphs (resp. forbidden induced subdigraphs), for several pairs \((g_1,g_2)\) of such graph (resp. digraph) colouring games \(g_1\) and \(g_2\), which define game chromatic numbers \(\chi_{g_1}\) and \( \chi_{g_2}\), we characterise the classes of graphs (resp. digraphs) such that, for any induced subgraph (resp. subdigraph) \(H\), the game chromatic numbers \(\chi_{g_1}(H)\) and \(\chi_{g_2}(H)\) of \(H\) are equal.
In Bodlaender’s original game, Alice begins. We also consider variants of this game where Bob begins or skipping turns is allowed [the author, Math. Methods Oper. Res. 69, No. 2, 235–250 (2009; Zbl 1161.91331)] and their generalizations to digraphs [the author, Discrete Math. 309, No. 11, 3564–3579 (2009; Zbl 1225.05105)]. By means of forbidden induced subgraphs (resp. forbidden induced subdigraphs), for several pairs \((g_1,g_2)\) of such graph (resp. digraph) colouring games \(g_1\) and \(g_2\), which define game chromatic numbers \(\chi_{g_1}\) and \( \chi_{g_2}\), we characterise the classes of graphs (resp. digraphs) such that, for any induced subgraph (resp. subdigraph) \(H\), the game chromatic numbers \(\chi_{g_1}(H)\) and \(\chi_{g_2}(H)\) of \(H\) are equal.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C17 | Perfect graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C15 | Coloring of graphs and hypergraphs |
| 91A43 | Games involving graphs |
Keywords:
equality perfect graph; game-perfect graph; trivially perfect graph; equality perfect digraph; game chromatic number; game colouring numberReferences:
| [1] | S.D. Andres,Game-perfect graphs, Math. Methods Oper. Res.69(2009), 235-250. 2.,Lightness of digraphs in surfaces and directed game chromatic number, Discrete Math.309(2009), 3594-3579. · Zbl 1225.05105 |
| [2] | S.D. Andres and E. Lock,Characterising and recognising game-perfect graphs, Discrete Math. Theor. Comput. Sci.21(2019), no. 1, Paper No. 6, 39pp. · Zbl 1411.05182 |
| [3] | T. Bartnicki, J. Grytczuk, H.A. Kierstead, and X. Zhu,The map-coloring game, Amer. Math. Monthly114(2007), 793-803. · Zbl 1247.05074 |
| [4] | H.L. Bodlaender,On the complexity of some coloring games, Internat. J. Found. Comput. Sci.2(1991), 133-147. · Zbl 0753.05061 |
| [5] | L. Cai and X. Zhu,Game chromatic index ofk-degenerate graphs, J. Graph Theory 36(2001), 144-155. · Zbl 0966.05028 |
| [6] | C. Charpentier,The coloring game on planar graphs with large girth, by a result on sparse cactuses, Discrete Math.340(2017), 1069-1073. · Zbl 1357.05103 |
| [7] | C. Charpentier, B. Effantin, and G. Paris,On the game coloring index ofF+decomposable graphs, Discrete Appl. Math.236(2018), 73-83. · Zbl 1377.05114 |
| [8] | C. Charpentier and ´E. Sopena,The incidence game chromatic number of(a, d)decomposable graphs, J. Discrete Algorithms31(2015), 14-25. · Zbl 1325.05074 |
| [9] | U. Faigle, W. Kern, H. Kierstead, and W.T. Trotter,On the game chromatic number of some classes of graphs, Ars Combin.35(1993), 143-150. · Zbl 0796.90082 |
| [10] | M.C. Golumbic,Trivially perfect graphs, Discrete Math.24(1978), 105-107. · Zbl 0384.05057 |
| [11] | D.J. Guan and X. Zhu,Game chromatic number of outerplanar graphs, J. Graph Theory30(1999), 67-70. · Zbl 0929.05032 |
| [12] | H.A. Kierstead,A simple competitive graph coloring algorithm, J. Combin. Theory Ser. B78(2000), 57-68. · Zbl 1024.05029 |
| [13] | J.W.H. Liu,The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl.11(1990), 134-172. · Zbl 0697.65013 |
| [14] | E. Lock,The structure ofgB-perfect graphs, Bachelor’s thesis, FernUniversit¨at in Hagen, 2016. |
| [15] | V. Neumann-Lara,The dichromatic number of a digraph, J. Combin. Theory Ser. B 33(1982), 265-270. · Zbl 0506.05031 |
| [16] | E. Sidorowicz,The game chromatic number and the game colouring number of cactuses, Inform. Process. Lett.102(2007), 147-151. · Zbl 1185.91058 |
| [17] | E.S. Wolk,The comparability graph of a tree, Proc. Amer. Math. Soc.13(1962), 789-795. · Zbl 0109.16402 |
| [18] | J. Wu and X. Zhu,Lower bounds for the game colouring number of partialk-trees and planar graphs, Discrete Math.308(2008), 2637-2642. · Zbl 1142.05032 |
| [19] | D. Yang and X. Zhu,Game colouring directed graphs, Electron. J. Combin.17(2010), no. 1, Research Paper 11, 19pp. · Zbl 1215.05075 |
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.
