Choice Number of k-Chromatic Graphs of Bounded Order

Discussion

For integers $ m,k\geq1 $ , let $ K_{m*k} $ denote the complete $ k $ -partite graph in which every part has size $ m $ . In one of the original papers on choosability, Erdos, Rubin and Taylor [ERT] proved that $ \text{ch}(K_{2*k})=k $ . Later, Ohba [Ohba] conjectured the following generalization: if $ |V(G)|\leq 2\chi(G)+1 $ , then TeX Embedding failed! .} This was proved by Noel, Reed and Wu [NRW12]. Theorem (Noel, Reed and Wu 2012) If $ |V(G)|\leq 2\chi(G)+1 $ , then $ \text{ch}(G)=\chi(G) $ . The above theorem implies that the above conjecture holds for $ m=2 $ . That is, if $ G $ is a $ k $ -chromatic graph on at most $ 2k $ vertices (in fact, at most $ 2k+1 $ vertices), then $ \text{ch}(G)=k=\text{ch}(K_{2*k}) $ . Kierstead [Kie00] proved that $ \text{ch}(K_{3*k})=\left\lceil\frac{4k-1}{3}\right\rceil $ . This was generalized by Noel, West, Wu and Zhu [NWWZ13] to the following: Theorem (Noel, West, Wu and Zhu 2013) For every graph $ G $ , \[\text{ch}(G)\leq\max\left\{\chi(G),\left\lceil\frac{|V(G)|+\chi(G)-1}{3}\right\rceil\right\}.\] Therefore, if $ G $ is a $ k $ -chromatic graph on at most $ 3k $ vertices, then $ \text{ch}(G)\leq \left\lceil\frac{4k-1}{3}\right\rceil=\text{ch}(K_{3*k}) $ . This shows that the conjecture is true for $ m=3 $ . Recently, Kierstead, Salmon and Wang [KSW14] proved the following: Theorem (Kierstead, Salmon and Wang 2014) $ \text{ch}(K_{4*k})=\left\lceil\frac{3k-1}{2}\right\rceil $ . However, it is not known whether the upper bound of $ \left\lceil\frac{3k-1}{2}\right\rceil $ holds for all $ k $ -chromatic graphs on at most $ 4k $ vertices. If true, it would verify the conjecture for $ m=4 $ . The following is a refinement of the conjecture. Conjecture (Noel 2013) For $ n\geq k\geq 1 $ there is a graph $ G_{n,k} $ such that \item $ G_{n,k} $ is a complete $ k $ -partite graph on $ n $ vertices, \item the stability number of $ G_{n,k} $ is $ \left\lceil n/k\right\rceil $ , and \item every $ k $ -chromatic graph $ G $ on at most $ n $ vertices satisfies $ \text{ch}(G)\leq \text{ch}(G_{n,k}) $ .