Graph choosability and double list colorability

• Autorzy: Fanai H. R.
• Języki publikacji: PL

Abstrakty

EN

In this paper, we give a sufficient condition for graph choosability, based on Combinatorial Nullstellensatz and a specific property, called "double list colorability", which means that there is a list assignment for which there are exactly two admissible colorings.

Słowa kluczowe

EN

list coloring; choosability

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2010
• Tom: Vol. 30, no. 3
• Strony: 271--276
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Fanai H. R.

• Sharif University of Technology Department of Mathematical Sciences P.O. Box 11155-9415 Tehran, Iran,

Bibliografia

• [1] S. Akbari, V.S. Mirrokni, B.S. Sadjad, A relation between choosability and uniquely list colorability, J. Combin. Theory Ser. B 96 (2006), 577–583.
• [2] N. Alon, M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.
• [3] C. Chao, Z. Chen, On uniquely 3-colorable graphs, Discrete Math. 112 (1993), 21–27.
• [4] P. Erdös, A.L. Rubin, H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979), 125–157.
• [5] C. Thomassen, The chromatic polynomial and list colorings, J. Combin. Theory Ser. B 99 (2009), 474–479.
• [6] V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Anal. 29 (1976), 3–10 [in Russian].
• [7] S. Xu, The size of uniquely colorable graphs, J. Combin. Theory Ser. B 50 (1990), 319–320.