Beyond Ohba's conjecture: a bound on the choice number of k-chromatic graphs with n vertices

DOI10.1016/J.EJC.2014.08.032zbMATH Open1301.05132arXiv1308.6739OpenAlexW2962798202WikidataQ123308432 ScholiaQ123308432MaRDI QIDQ458608FDOQ458608

Authors: Jonathan A. Noel, Douglas B. West, Hehui Wu, Xuding Zhu 

Publication date: 8 October 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $extch(G)$ denote the choice number of a graph $G$ (also called "list chromatic number" or "choosability" of $G$). Noel, Reed, and Wu proved the conjecture of Ohba that $extch(G)=chi(G)$ when $|V(G)|le2chi(G)+1$. We extend this to a general upper bound: $extch(G)lemaxchi(G),lceil(|V(G)|+chi(G)-1)/3ceil$. Our result is sharp for $|V(G)|le3chi(G)$ using Ohba's examples, and it improves the best-known upper bound for $extch(K_{4,dots,4})$.

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

Recommendations

• On choosability of some complete multipartite graphs and Ohba's conjecture
• Some bounds for the \(b\)-chromatic number of a graph
• New bounds for the chromatic number of graphs
• Bounds for the chromatic number of a graph
• scientific article; zbMATH DE number 6383843
• On bounding the chromatic number of L-graphs
• A bound of the vertex-distinguishing total chromatic number of graphs
• Upper bounds on the \(b\)-chromatic number and results for restricted graph classes
• Reexploring the upper bound for the chromatic number of graphs
• scientific article; zbMATH DE number 4108789

zbMATH Keywords

choosabilitylist chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Ohba's conjecture is true for graphs with independence number at most three
• Choice number of some complete multi-partite graphs
• On the choosability of complete multipartite graphs with part size three
• List colourings of graphs
• Graph colorings with local constraints -- a survey
• On chromatic‐choosable graphs
• Title not available (Why is that?)
• Ohba's conjecture for graphs with independence number five
• Title not available (Why is that?)
• List colouring when the chromatic number is close to the order of the graph
• Title not available (Why is that?)
• Distinct representatives of subsets
• Choice Numbers of Graphs: a Probabilistic Approach
• Graphs with $\chi=\Delta$ Have Big Cliques
• Title not available (Why is that?)
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• On the asymptotic value of the choice number of complete multi‐partite graphs
• Coloring Graphs with Dense Neighborhoods

Cited In (4)

• Chromatic-choosability of hypergraphs with high chromatic number
• A Proof of a Conjecture of Ohba
• On the choice number of complete multipartite graphs with part size four
• Interview with Douglas West

This page was built for publication: Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices

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