List coloring of Cartesian products of graphs (Q2501567): Difference between revisions

Assume that each vertex \(v\) of a graph \(G\) is equipped with a list \(L(v)\) of \(k\) colors. Then the list chromatic number \(\chi_\ell(G)\) is the smallest integer \(k\) such that, for every list assignment \(L\), there exists a proper vertex coloring \(c\) of \(G\) with \(c(v)\in L(v)\) for every vertex \(v\) of \(G\). The coloring number col\((G)\) of \(G\) is the smallest integer \(d\) for which there exists an ordering \(v_1, v_2, \dots, v_n\) of the vertices of \(G\) such that \(v_i\) has at most \(d-1\) neighbors among \(v_1, \dots, v_{i-1}\). The authors prove that \(\chi_\ell(G\times H)\leq\min\{\chi_\ell(G)+\text{col}(H), \text{col}(G)+\chi_\ell(H)\}-1,\) where \(G\times H\) is the Cartesian product of \(G\) and \(H\). They also give examples showing that the bound is tight.