Improper Choosability and Property B
Ross J. Kang · Journal of Graph Theory · 2012
Abstract A fundamental connection between list vertex colorings of graphs and Property B (also known as hypergraph 2‐colorability) was already known to Erdős, Rubin, and Taylor ((1980), 125–157). In this article, we draw similar connections for improper list colorings. This extends results of Kostochka (Electron J Combin 9 (2002)), Alon (Combin Probab Comput 1 (1992), 107–114; (1993), 1–33; Random Structures Algorithms 16 (2000), 364–368), and Král’ and Sgall (J Graph Theory 49 (2005), 177–186) for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.