List coloring of Cartesian products of graphs
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.
- Asymptotically good list-colorings
- Graph colorings with local constraints -- a survey
- scientific article; zbMATH DE number 446487 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 3563170 (Why is no real title available?)
- scientific article; zbMATH DE number 1341914 (Why is no real title available?)
- scientific article; zbMATH DE number 1496580 (Why is no real title available?)
- List colourings of graphs
- Criticality, the list color function, and list coloring the Cartesian product of graphs
- Alon-Tarsi numbers of direct products
- List coloring a Cartesian product with a complete bipartite factor
- ON THE EDGE-CONNECTIVITY OF CARTESIAN PRODUCT GRAPHS
- On the number of list‐colorings
- First-fit coloring of Cartesian product graphs and its defining sets
- scientific article; zbMATH DE number 7637228 (Why is no real title available?)
- DP‐coloring Cartesian products of graphs
- Flexible list colorings: maximizing the number of requests satisfied
- On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
- List coloring the Cartesian product of a complete graph and complete bipartite graph
- On the -chromatic numbers of the Cartesian products of graphs
- On the DP-chromatic number of Cartesian products of critical graphs
This page was built for publication: List coloring of Cartesian products of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2501567)
