Coloring bipartite graphs with semi-small list size

DOI10.1007/S00026-022-00633-ZMaRDI QIDQ6065679zbMATH OpenOpenAlexFDO

Authors Daniel Zhu

Publication date 15 November 2023

Published in Annals of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

choosabilityindependent setslist chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Extremal set theory (05D05)

Abstract: Recently, Alon, Cambie, and Kang introduced asymmetric list coloring of bipartite graphs, where the size of each vertex's list depends on its part. For complete bipartite graphs, we fix the list sizes of one part and consider the resulting asymptotics, revealing an invariant quantity instrumental in determining choosability across most of the parameter space. By connecting this quantity to a simple question on independent sets of hypergraphs, we strengthen bounds when a part has list size 2. Finally, we state via our framework a conjecture on general bipartite graphs, unifying three conjectures of Alon-Cambie-Kang.

Recommendations

• List colorings with distinct list sizes, the case of complete bipartite graphs
• List colorings with distinct list sizes, the case of complete bipartite graphs
• Partial list colouring of certain graphs
• Dynamic list coloring of bipartite graphs
• Coloring complete bipartite graphs from random lists
• Coloring graphs from lists with bounded size of their union
• Coloring problems on bipartite graphs of small diameter
• Coloring complete and complete bipartite graphs from random lists
• List coloring of complete multipartite graphs
• On list \(k\)-coloring convex bipartite graphs

Cites work

• A guided tour of Chernoff bounds
• Asymmetric list sizes in bipartite graphs
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• The choice number of random bipartite graphs
• The list chromatic number of graphs with small clique number
• What is... the Schwarzian derivative?

Cited in

(4)

• On list \(k\)-coloring convex bipartite graphs
• Balanced list edge-colourings of bipartite graphs
• Dynamic list coloring of bipartite graphs
• Packing colourings in complete bipartite graphs and the inverse problem for correspondence packing

This page was built for publication: Coloring bipartite graphs with semi-small list size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065679)