List coloring of Cartesian products of graphs |
| |
Authors: | Mieczys?aw Borowiecki Daniel Král’ |
| |
Institution: | a Faculty of Mathematics, Computer Sciences and Econometrics, University of Zielona Gora, Podgórna 50, 65-246 Zielona Góra, Poland b Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University in Košice, Jesenná 5, 041 54 Košice, Slovakia c Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague, Czech Republic |
| |
Abstract: | 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)∈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 χ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 χl(G) and χl(H). On the other hand, we prove that χl(G×H)?min{χl(G)+col(H),col(G)+χl(H)}-1 and construct examples of graphs G and H for which our bound is tight. |
| |
Keywords: | Graph coloring List coloring Cartesian product of graphs Products of graph |
本文献已被 ScienceDirect 等数据库收录! |
|