Choice number of 3-colorable elementary graphs (Q1356789): Difference between revisions

The choice number \(\text{ch}(G)\) of a graph \(G= (V,E)\) is the smallest number \(k\) for which, for any assignment of a list \(L(v)\) of \(k\) colors to every vertex \(v\in V\), it is possible to color properly the vertices of \(G\) so that every vertex gets a color from its list. Certainly, \(\chi(G)\leq \text{ch}(G)\) for every graph \(G\), with equality holding true for trees, cycles, wheels, line-graphs of bipartite graphs and complements of triangle-free graphs, to mention just a few examples. The authors show that \(\chi(G)= \text{ch}(G)\) if \(G\) belongs to a restricted family of claw-free graphs, namely to the so-called elementary graphs with \(\omega(G)\leq 3\). This result supports their conjecture that every claw-free graph \(G\) satisfies the choice chromatic equality, which is more general than the well-known list-chromatic conjecture.