Extensions of Galvin's Theorem

Graph Coloring;List Coloring;Galvin's Theorem

Levit, Maxwelladvisor:Cheriyan, Joseph ; affiliation1:Faculty of Mathematics ; Cheriyan, Joseph ;

University of Waterloo

关键词: List Coloring;    Galvin'    Master Thesis;    s Theorem;    Graph Coloring;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13211/3/Levit_Maxwell.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

We discuss problems in list coloring with an emphasis on techniques that utilize oriented graphs. Our central theme is Galvin's resolution of the Dinitz problem (Galvin. J. Comb. Theory, Ser. B 63(1), 1995, 153--158).We survey the related work of Alon and Tarsi (Combinatorica 12(2) 1992, 125--134) and H;;{a}ggkvist and Janssen (Combinatorics, Probability & Computing 6(3) 1997,295--313). We then prove two new extensions of Galvin's theorem.