Geodesic
Game list colouring of graphs
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
We consider the two-player game defined as follows. Let $(G,L)$ be a graph $G$ with a list assignment $L$ on its vertices. The two players, Alice and Bob, play alternately on $G$, Alice having the first move. Alice's goal is to provide an $L$-colouring of $G$ and Bob's goal is to prevent her from doing so. A move consists in choosing an uncoloured vertex $v$ and assigning it a colour from the set $L(v)$. Adjacent vertices of the same colour must not occur. This game will be called game list colouring. The game choice number of $G$, denoted by ch$_g(G)$, is defined as the least $k$ such that Alice has a winning strategy for any $k$-list assignment of $G$. We characterize the class of graphs with ch$_g(G)\le 2$ and determine the game choice number for some classes of graphs.
DOI : 10.37236/944
Classification : 05C15, 05C75, 91A05
Mots-clés : two-player game, game choice number 
M. Borowiecki; E. Sidorowicz; Zs. Tuza. Game list colouring of graphs. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/944
@article{10_37236_944,
     author = {M. Borowiecki and E. Sidorowicz and Zs. Tuza},
     title = {Game list colouring of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/944},
     zbl = {1114.05033},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/944/}
}
TY  - JOUR
AU  - M. Borowiecki
AU  - E. Sidorowicz
AU  - Zs. Tuza
TI  - Game list colouring of graphs
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/944/
DO  - 10.37236/944
ID  - 10_37236_944
ER  - 
%0 Journal Article
%A M. Borowiecki
%A E. Sidorowicz
%A Zs. Tuza
%T Game list colouring of graphs
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/944/
%R 10.37236/944
%F 10_37236_944

Cité par Sources :