Improper choosability and property B
From MaRDI portal
Publication:5325946
DOI10.1002/JGT.21680zbMATH Open1269.05035arXiv1205.4283OpenAlexW3124063821MaRDI QIDQ5325946FDOQ5325946
Authors: Ross J. Kang Edit this on Wikidata
Publication date: 31 July 2013
Published in: Journal of Graph Theory (Search for Journal in Brave)
Abstract: A fundamental connection between list vertex colourings of graphs and Property B (also known as hypergraph 2-colourability) was already known to ErdH{o}s, Rubin and Taylor. In this article, we draw similar connections for improper list colourings. This extends results of Kostochka, Alon, and Kr'al' and Sgall for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.
Full work available at URL: https://arxiv.org/abs/1205.4283
Recommendations
Cites Work
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- Title not available (Why is that?)
- Title not available (Why is that?)
- Every planar graph is 5-choosable
- Graph colouring and the probabilistic method
- A note on list improper coloring of plane graphs
- List improper colorings of planar graphs with prescribed girth
- Improper choosability of graphs of nonnegative characteristic
- Title not available (Why is that?)
- Combinatorial Nullstellensatz
- List Improper Colourings of Planar Graphs
- A Grötzsch-Type Theorem for List Colourings with Impropriety One
- A note on list improper coloring planar graphs
- Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
- Planar graphs are 1-relaxed, 4-choosable
- On a property of families of sets
- Improved bounds and algorithms for hypergraph 2-coloring
- Title not available (Why is that?)
- Improper choosability of graphs and maximum average degree
- On a combinatorial problem. II
- List colourings of planar graphs
- Choice Numbers of Graphs: a Probabilistic Approach
- On the asymptotic value of the choice number of complete multi‐partite graphs
- Improper choosability of graphs embedded on the surface of genus \(r\)
- On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
- The \(t\)-improper chromatic number of random graphs
- A note on \((3,1)^*\)-choosable toroidal graphs
- On A Combinatorial Problem III
- On generalized list colourings of graphs
- Generalized list colourings of graphs
- Defective choosability of graphs with no edge-plus-independent-set minor
- On a generalization of Rubin's theorem
- The existence of panchromatic colourings for uniform hypergraphs
- Defective choosability results for outerplanar and related graphs
- Coloring graphs from lists with bounded size of their union
- Defective choosability of graphs without small minors
Cited In (6)
This page was built for publication: Improper choosability and property B
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5325946)
