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

Abstract: Let

e x t c h (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

e x t c h (G) = c h i (G)

when

| V (G) | l e 2 c h i (G) + 1

. We extend this to a general upper bound:

e x t c h (G) l e m a x c h i (G), l c e i l (| V (G) | + c h i (G) - 1) / 3 c e i l

. Our result is sharp for

| V (G) | l e 3 c h i (G)

using Ohba's examples, and it improves the best-known upper bound for

e x t c h (K_{4, d o t s, 4})

.

Recommendations

Cites work

Cited in

(5)

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