Beyond Ohba's Conjecture: A bound on the choice number of kk-chromatic graphs with nn vertices

preprint2014arXivOpen access

Abstract

Let ch(G)\text{ch}(G) denote the choice number of a graph GG (also called "list chromatic number" or "choosability" of GG). Noel, Reed, and Wu proved the conjecture of Ohba that ch(G)=χ(G)\text{ch}(G)=χ(G) when ∣V(G)∣≤2χ(G)+1|V(G)|\le 2χ(G)+1. We extend this to a general upper bound: ch(G)≤max⁡{χ(G),⌈(∣V(G)∣+χ(G)−1)/3⌉}\text{ch}(G)\le \max\{χ(G),\lceil({|V(G)|+χ(G)-1})/{3}\rceil\}. Our result is sharp for ∣V(G)∣≤3χ(G)|V(G)|\le 3χ(G) using Ohba's examples, and it improves the best-known upper bound for ch(K4,…,4)\text{ch}(K_{4,\dots,4}).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.