Characterising and recognising game-perfect graphs

zbMATH Open1411.05182arXiv1810.12439MaRDI QIDQ5377789FDOQ5377789

Authors: Dominique Andres, Edwin Lock 

Publication date: 27 May 2019

Abstract: Consider a vertex colouring game played on a simple graph with $k$ 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 $g_B$, the breaker makes the first move. Our main focus is on the class of $g_B$-perfect graphs: graphs such that for every induced subgraph $H$, the game $g_B$ played on $H$ admits a winning strategy for the maker with only $omega(H)$ colours, where $omega(H)$ denotes the clique number of $H$. Complementing analogous results for other variations of the game, we characterise $g_B$-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 $g_B$-perfect graphs.

Full work available at URL: https://arxiv.org/abs/1810.12439

Recommendations

• Game-perfect graphs
• On characterizing game-perfect graphs by forbidden induced subgraphs
• Game-perfect Graphs with Clique Number 2
• The complexity of coloring games on perfect graphs
• A characterization of \(b\)-perfect graphs

zbMATH Keywords

perfect graphgame chromatic numbergraph colouring gamegame-perfect graphclique module decompositiondominating edge decompositionforbidden induced subgraph characterisation

Mathematics Subject Classification ID

2-person games (91A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Perfect graphs (05C17)

Cited In (10)

• Game-perfect graphs
• Game-perfect semiorientations of forests
• Seurat games on Stockmeyer graphs
• The connected greedy coloring game
• On characterizing game-perfect graphs by forbidden induced subgraphs
• Equality perfect graphs and digraphs
• Game-perfect digraphs
• The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
• \textsf{PSPACE}-hardness of variants of the graph coloring game
• Game-perfect Graphs with Clique Number 2

This page was built for publication: Characterising and recognising game-perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377789)