Publication details
List coloring of Cartesian products of graphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.disc.2006.03.062 |
| Keywords | graph coloring; list coloring; Cartesian product of graphs; products of graph |
| Description | A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v) E L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by chi(l) (G). We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of chi(l) (G) and chi(l) (H). On the other hand, we prove that chi(l) (G x H) <= min{chi(l)(G) + col(H), col(G) + chi(l)(H)} - 1 and construct examples of graphs G and H for which our bound is tight. (c) 2006 Elsevier B.V. All rights reserved. |