2019/10/28 by Zhu, Jialu, Zhu, Xuding
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.12509
Let ϕ(k) be the minimum number of vertices in a non-k-choosable k-chromatic graph. The Ohba conjecture, confirmed by Noel, Reed and Wu, asserts that ϕ(k) ≥ 2k+2. This bound is tight if k is even. If k is odd, then it is known that ϕ(k) ≤ 2k+3 and it is conjectured by Noel that ϕ(k) = 2k+3. For a multi-set λ=\k1,k2, …, kq\ of positive integers, let kλ = ∑i=1q ki. A λ-list assignment of G is a kλ-list assignment L for which the colour set ∪v ∈ V(G)L(v) can be partitioned into the disjoint union C1 ∪ C2 ∪ … ∪ Cq of q sets so that for each i and each vertex v of G, |L(v) ∩ Ci| ≥ ki. We say G is λ-choosable if G is L-colourable for any λ-list assignment L of G. Let ϕ(λ) be the minimum number of vertices in a non-λ-choosable kλ-chromatic graph. Let 1λ be the multiplicity of 1 in λ, and let oλ be the number of elements in λ that are odd integers. We prove that if 1λ ≠ kλ, then 2kλ+1λ+2 \leqslant ϕ(λ) \leqslant 2kλ+ oλ+2. In particular, if 1λ=oλ=t, i.e. λ contains no odd integer greater than 1, then ϕ(λ) = 2kλ+t+2. We also prove that ϕ(λ) \leqslant 2kλ+5 1λ+3. In particular, if 1λ=0, then 2kλ+2 \leqslant ϕ(λ) \leqslant 2kλ+3.