Criticality, the list color function, and list coloring the Cartesian product of graphs (Q2041704)

A graph \(G\) is chromatic-choosable if its chromatic number equals its list chromatic number. By considering combining coloring criticality, the concept of strongly chromatic-choosable graphs is introduced and initially studied. For an integer \(k\), a graph \(G\) is strong \(k\)-chromatic-choosable if \(\chi(G) = k\) and every \((k-1)\)-assignment for which \(G\) is not list-colorable has the property that the lists are the same for all vertices. A sufficient condition is derived for the existence of at least two list colorings of strongly chromatic-choosable graphs, which is applied to prove an upper bound for the list chromatic number of the Cartesian product of a strong chromatic-choosable graph and a traceable graph (one that has a Hamilton path). The list coloring analogue of the chromatic polynomial, the list color function, is also introduced. By utilizing the list color function, it is shown that the upper bound mentioned above is infact sharp. Other applications of the list color function also lead to the determination of the list chromatic numbers of the Cartesian product of certain strong chromatic-choosable graphs and a star. Several open problems are raised in the paper, which seem to be interesting.