Geodesic
Characterising and recognising game-perfect graphs
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_1_a6,
     author = {Andres, Dominique and Lock, Edwin},
     title = {Characterising and recognising game-perfect graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-6/}
}
TY  - JOUR
AU  - Andres, Dominique
AU  - Lock, Edwin
TI  - Characterising and recognising game-perfect graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-6/
DO  - 10.23638/DMTCS-21-1-6
LA  - en
ID  - DMTCS_2019_21_1_a6
ER  - 
%0 Journal Article
%A Andres, Dominique
%A Lock, Edwin
%T Characterising and recognising game-perfect graphs
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-6/
%R 10.23638/DMTCS-21-1-6
%G en
%F DMTCS_2019_21_1_a6
Andres, Dominique; Lock, Edwin. Characterising and recognising game-perfect graphs. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi : 10.23638/DMTCS-21-1-6. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-6/

Cité par Sources :