Geodesic
Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We present a purely combinatorial proof of Alon and Tarsi's Theorem about list colorings and orientations of graphs. More precisely, we describe a winning strategy for Mrs. Correct in the corresponding coloring game of Mr. Paint and Mrs. Correct. This strategy produces correct vertex colorings, even if the colors are taken from lists that are not completely fixed before the coloration process starts. The resulting strengthening of Alon and Tarsi's Theorem leads also to strengthening of its numerous repercussions. For example we study upper bounds for list chromatic numbers of bipartite graphs and list chromatic indices of complete graphs. As real life application, we examine a chess tournament time scheduling problem with unreliable participants.
DOI : 10.37236/285
Classification : 91A43, 05C15, 05C20
Mots-clés : Alon and Tarsi's theorem, list coloring and orientation of graphs, combinatoric, time scheduling with unreliable participants 
@article{10_37236_285,
     author = {Uwe Schauz},
     title = {Flexible color lists in {Alon} and {Tarsi's} theorem, and time scheduling with unreliable participants},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/285},
     zbl = {1192.91045},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/285/}
}
TY  - JOUR
AU  - Uwe Schauz
TI  - Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/285/
DO  - 10.37236/285
ID  - 10_37236_285
ER  - 
%0 Journal Article
%A Uwe Schauz
%T Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/285/
%R 10.37236/285
%F 10_37236_285
Uwe Schauz. Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/285

Cité par Sources :