Improper choosability and property B

DOI10.1002/JGT.21680MaRDI QIDQ5325946zbMATH OpenOpenAlexFDO

Authors Ross J. Kang

Publication date 31 July 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.4283

zbMATH Keywords

hypergraph 2-colorabilityimproper list colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

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.

Recommendations

• List Improper Colourings of Planar Graphs
• Choosability in simple hypergraphs
• A note on list improper coloring of plane graphs
• On improperly chromatic-choosable graphs
• List improper coloring of graphs of nonnegative characteristic

Cites work

• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• scientific article; zbMATH DE number 3999967 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• A Grötzsch-Type Theorem for List Colourings with Impropriety One
• A note on \((3,1)^*\)-choosable toroidal graphs
• A note on list improper coloring of plane graphs
• A note on list improper coloring planar graphs
• Choice Numbers of Graphs: a Probabilistic Approach
• Coloring graphs from lists with bounded size of their union
• Combinatorial Nullstellensatz
• Defective choosability of graphs with no edge-plus-independent-set minor
• Defective choosability of graphs without small minors
• Defective choosability results for outerplanar and related graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph is 5-choosable
• Every toroidal graph without adjacent triangles is \((4,1)^{*}\)-choosable
• Generalized list colourings of graphs
• Graph colouring and the probabilistic method
• Improper choosability of graphs and maximum average degree
• Improper choosability of graphs embedded on the surface of genus r
• Improper choosability of graphs of nonnegative characteristic
• Improved bounds and algorithms for hypergraph 2-coloring
• List Improper Colourings of Planar Graphs
• List colourings of planar graphs
• List improper colorings of planar graphs with prescribed girth
• On A Combinatorial Problem III
• On a combinatorial problem. II
• On a generalization of Rubin's theorem
• On a property of families of sets
• On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
• On generalized list colourings of graphs
• On the asymptotic value of the choice number of complete multi‐partite graphs
• Planar graphs are 1-relaxed, 4-choosable
• The \(t\)-improper chromatic number of random graphs
• The existence of panchromatic colourings for uniform hypergraphs

Cited in

(6)

• On generalized choice and coloring numbers
• Distance-two coloring of sparse graphs
• List Coloring with a Bounded Palette
• Improper colouring of graphs with no odd clique minor
• On two problems of defective choosability of graphs
• On improperly chromatic-choosable graphs

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)