Characterising and recognising game-perfect graphs

Journal article

Consider a vertex colouring game played on a simple graph with 𝑘 permissible colours. Two players, a maker and a breaker, take turns to colour an uncoloured vertex such that adjacent vertices receive different colours. The game ends once the graph is fully coloured, in which case the maker wins, or the graph can no longer be fully coloured, in which case the breaker wins. In the game 𝑔_𝐵, the breaker makes the first move. Our main focus is on the class of 𝑔_𝐵-perfect graphs: graphs such that for every induced subgraph 𝐻, the game 𝑔_𝐵 played on 𝐻 admits a winning strategy for the maker with only 𝜔(𝐻) colours, where 𝜔(𝐻) denotes the clique number of 𝐻. Complementing analogous results for other variations of the game, we characterise 𝑔_𝐵-perfect graphs in two ways, by forbidden induced subgraphs and by explicit structural descriptions. We also present a clique module decomposition, which may be of independent interest, that allows us to efficiently recognise 𝑔_𝐵-perfect graphs.

Authors: Andres, D; Lock, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Episciences.org
• Journal: Discrete Mathematics & Theoretical Computer Science
• Volume: 21
• Issue: 1
• Article number: 6
• Publication date: 2019-05-23
• Acceptance date: 2019-04-22
• DOI: 10.23638/DMTCS-21-1-6
• EISSN: 1365-8050
• ISSN: 1462-7264
• Language: English
• Keywords: graph colouring game; forbidden induced subgraph characterisation; FFR; game-perfect graph; game chromatic number; clique module decomposition; dominating edge decomposition; perfect graph