Improper Choosability and Property B
Author:
- 18 June 2012
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 73 (3) , 342-353
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.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- On a generalization of Rubin's theoremJournal of Graph Theory, 2011
- Planar graphs are 1-relaxed, 4-choosableEuropean Journal of Combinatorics, 2010
- On the asymptotic value of the choice number of complete multi‐partite graphsJournal of Graph Theory, 2006
- Improper choosability of graphs and maximum average degreeJournal of Graph Theory, 2006
- Coloring graphs from lists with bounded size of their unionJournal of Graph Theory, 2005
- Defective choosability of graphs with no edge‐plus‐independent‐set minorJournal of Graph Theory, 2003
- List improper colorings of planar graphs with prescribed girthDiscrete Mathematics, 2000
- Restricted colorings of graphs1993
- On A Combinatorial Problem IIICanadian Mathematical Bulletin, 1969
- On a combinatorial problem. IIActa Mathematica Hungarica, 1964