Flexible color lists in alon and tarsi's theorem, and time scheduling with unreliable participants

Uwe Schauz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalElectronic Journal of Combinatorics
Volume17
Issue number1
DOIs
Publication statusPublished - 2010
Externally publishedYes

Cite this