Chromatic-choosability of hypergraphs with high chromatic number

MaRDI QIDQ668048zbMATH OpenFDO

Authors Wei Wang, Jianguo Qian

Publication date 5 March 2019

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

Full work available at URL https://arxiv.org/abs/1807.08273, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p5

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

zbMATH Keywords

chromatic numberhypergraphslist chromatic number

Mathematics Subject Classification ID

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

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)$.

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

Cites work

• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1341914 (Why is no real title available?)
• scientific article; zbMATH DE number 1123764 (Why is no real title available?)
• A proof of a conjecture of Ohba
• Asymptotically good list-colorings
• Betti Numbers of Hypergraphs
• Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
• Choice number of 3-colorable elementary graphs
• Choice number of some complete multi-partite graphs
• 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
• Graph colorings with local constraints -- a survey
• Hajós' theorem for list colorings of hypergraphs
• Hypergraph containers
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• Hypergraph list coloring and Euclidean Ramsey theory
• List coloring hypergraphs
• List colouring when the chromatic number is close to the order of the graph
• List colourings of regular hypergraphs
• On chromatic‐choosable graphs
• On improperly chromatic-choosable graphs
• On the choosability of complete multipartite graphs with part size three
• Some upper bounds on the total and list chromatic numbers of multigraphs
• Towards a version of Ohba's conjecture for improper colorings

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)