Minimum non-chromatic-choosable graphs with given chromatic number
Jialu Zhu, Xuding Zhu · Canadian Journal of Mathematics · 2024
Abstract A graph G is called chromatic-choosable if χ ( G ) = c h ( G ) $\chi (G)=ch(G)$ chi left parenthesis upper G right parenthesis equals c h left parenthesis upper G right parenthesis . A natural problem is to determine the minimum number of vertices in a non-chromatic-choosable graph with given chromatic number. It was conjectured by Ohba, and proved by Noel, Reed, and Wu that k -chromatic graphs G with | V ( G ) | ≤ 2 k + 1 $|V(G)| \le 2k+1$ StartAbsoluteValue upper V left parenthesis upper G right parenthesis EndAbsoluteValue less than or equals 2 k plus 1 are chromatic-choosable. This upper bound on | V ( G ) | $|V(G)|$ StartAbsoluteValue upper V left parenthesis upper G right parenthesis EndAbsoluteValue is tight. It is known that if k is even, then G = K 3 ⋆ ( k / 2 + 1 ) , 1 ⋆ ( k / 2 − 1 ) $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ upper G equals upper K Subscript 3 star left parenthesis k divided by 2 plus 1 right parenthesis comma 1 star left parenthesis k divided by 2 minus 1 right parenthesis and G = K 4 , 2 ⋆ ( k − 1 ) $G=K_{4, 2 \star (k-1)}$ upper G equals upper K Subscript 4 comma 2 star left parenthesis k minus 1 right parenthesis are non-chromatic-choosable k -chromatic graphs with