Chromatic λ‐choosable and λ‐paintable graphs
Jialu Zhu, Xuding Zhu · Journal of Graph Theory · 2021
Abstract Let be the minimum number of vertices in a non‐‐choosable ‐chromatic graph. The Ohba conjecture, confirmed by Noel, Reed and Wu, asserts that . This bound is tight if is even. If is odd, then it is known that and it is conjectured by Noel that . For a multiset of positive integers, let . For positive integer , let be the multiplicity of in , and let be the number of elements in that are odd integers. A ‐list assignment of is a list assignment such that the colour set can be partitioned into the disjoint union of sets so that for each and each vertex of , . We say is ‐choosable if is ‐colourable for any ‐list assignment of . We say is trivial if consists of copies of 1. It is easy to see that if is trivial, then ‐choosable is equivalent to ‐colourable. For any nontrivial , let be the minimum number of vertices in a non‐‐choosable ‐chromatic graph. We prove that for any nontrivial , . In particular, if , that is, contains no odd integer greater than 1, then . We also prove that . In particular, if , then . We then introduce the concept of ‐paintability of graphs, which is an online version of ‐choosability. Let be the minimum number of vertices in a non‐‐paintable ‐chromatic graph. We determine the value of when each integer in is at most 2.