Chromatic-choosability of hypergraphs with high chromatic number

zbMATH Open1411.05096arXiv1807.08273MaRDI QIDQ668048FDOQ668048

Authors: Wei Wang, Jianguo Qian 

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: It was conjectured by Ohba and confirmed recently by Noel et al. that, for any graph $G$, if $|V(G)|le2chi(G)+1$ then $ch{i}_l(G)=chi(G)$. This indicates that the graphs with high chromatic number are chromatic-choosable. We show that this is also the case for uniform hypergraphs and further propose a generalized version of Ohba's conjecture: for any $r$-uniform hypergraph $H$ with $rgeq2$, if $|V(H)|lerchi(H)+r-1$ then $ch{i}_l(H)=chi(H)$. We show that the condition of the proposed conjecture is sharp by giving two classes of $r$-uniform hypergraphs $H$ with $|V(H)|=rchi(H)+r$ and $ch{i}_l(H)>chi(H)$. To support the conjecture, we give two classes of $r$-uniform hypergraphs $H$ with $|V(H)|=rchi(H)+r-1$ and prove that $ch{i}_l(H)=chi(H)$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Chromatic choosability of a class of complete multipartite graphs
• On chromatic‐choosable graphs
• On choosability of some complete multipartite graphs and Ohba's conjecture
• Ohba's conjecture is true for graphs with independence number at most three
• On the choosability of some graphs

zbMATH Keywords

chromatic numberhypergraphslist chromatic number

Mathematics Subject Classification ID

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

Cites Work

• Betti Numbers of Hypergraphs
• Title not available (Why is that?)
• Some upper bounds on the total and list chromatic numbers of multigraphs
• Choice number of some complete multi-partite graphs
• On the choosability of complete multipartite graphs with part size three
• Graph colorings with local constraints -- a survey
• Title not available (Why is that?)
• On chromatic‐choosable graphs
• Hypergraph containers
• List colouring when the chromatic number is close to the order of the graph
• Title not available (Why is that?)
• List coloring hypergraphs
• List colourings of regular hypergraphs
• Hypergraph list coloring and Euclidean Ramsey theory
• Choice number of 3-colorable elementary graphs
• Asymptotically good list-colorings
• Title not available (Why is that?)
• Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• Coloring Graphs with Dense Neighborhoods
• Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker
• A proof of a conjecture of Ohba
• On improperly chromatic-choosable graphs
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• Towards a version of Ohba's conjecture for improper colorings
• Hajós' theorem for list colorings of hypergraphs

Cited In (3)

• Choosability in simple hypergraphs
• Dense uniform hypergraphs have high list chromatic number
• Defective colorings on \(k\)-uniform hypergraphs

This page was built for publication: Chromatic-choosability of hypergraphs with high chromatic number

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