Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants (Q2380445)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants |
scientific article |
Statements
Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants (English)
0 references
26 March 2010
0 references
This paper presents a purely combinatorial proof of Alon and Tarsi's theorem about list coloring and orientations of graphs. It describes a winning strategy for Mrs. Correct in the corresponding coloring game of Mr. Paint and Mrs. Correct. This strategy produces vertex coloring, 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 to strengthening of its numerous repercussions. As real life application, it examines a chess tournament time scheduling problem with unreliable participants.
0 references
Alon and Tarsi's theorem
0 references
list coloring and orientation of graphs
0 references
combinatoric
0 references
time scheduling with unreliable participants
0 references