complete multipartite graph


List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

Choice number of complete multipartite graphs with parts of size 4

Author(s):

Question   What is the choice number of $ K_{4*k} $ for general $ k $?

Keywords: choosability; complete multipartite graph; list coloring

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture   If $ G $ is a $ k $-chromatic graph on at most $ mk $ vertices, then $ \text{ch}(G)\leq \text{ch}(K_{m*k}) $.

Keywords: choosability; complete multipartite graph; list coloring

Ohba's Conjecture ★★

Author(s): Ohba

Conjecture   If $ |V(G)|\leq 2\chi(G)+1 $, then $ \chi_\ell(G)=\chi(G) $.

Keywords: choosability; chromatic number; complete multipartite graph; list coloring

Syndicate content