Improper choosability and Property B

Abstract

A fundamental connection between list vertex colourings of graphs and Property B (also known as hypergraph 2-colourability) was already known to Erdős, Rubin and Taylor. In this article, we draw similar connections for improper list colourings. This extends results of Kostochka, Alon, and Král' and Sgall for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.

12 pages

References in corpus (1)

• The t-improper chromatic number of random graphs

Cited by in corpus (3)

• Improper coloring of graphs with no odd clique minor
• List colouring with a bounded palette
• Distance-two coloring of sparse graphs