Geodesic
Game list colouring of graphs
The electronic journal of combinatorics, Tome 14 (2007)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
M. Borowiecki; E. Sidorowicz; Zs. Tuza. Game list colouring of graphs. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/944

Cité par Sources :