List coloring of Cartesian products of graphs

BOROWIECKI, M; S JENDROL; Daniel KRÁĽ a J MISKUF. List coloring of Cartesian products of graphs. Discrete Mathematics. AMSTERDAM: Elsevier B. V., 2006, roč. 306, č. 16, s. 1955-1958. ISSN 0012-365X. Dostupné z: https://doi.org/10.1016/j.disc.2006.03.062.

Základní údaje

Originální název

List coloring of Cartesian products of graphs

Autoři

BOROWIECKI, M; S JENDROL; Daniel KRÁĽ a J MISKUF

Vydání

Discrete Mathematics, AMSTERDAM, Elsevier B. V. 2006, 0012-365X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.347

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1016/j.disc.2006.03.062

UT WoS

000240173300013

Klíčová slova anglicky

graph coloring; list coloring; Cartesian product of graphs; products of graph

---

Anotace

V originále

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.