Bounds on L(2,1)-choice number of Cartesian products of paths and spiders

Haiying Zhou, Wai Chee Shiu, Peter Che Bor Lam

Research output: Contribution to journalArticlepeer-review

Abstract

For a given graph G = (V,E), let L(G) = {L(v) : v ∈ V } be a prescribed list assignment. G is L-L(2, 1)-colorable if there exists a vertex labeling f of G such that [function of](v) ∈ L(v) for all v ∈ V ; |[function of](u)-[function of](v)| ≥ 2 if d^sub G^(u, v) = 1; and |[function of](u)-[function of](v)| ≥ 1 if d^sub G^(u, v) = 2. If G is L-L(2, 1)-colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V , then G is said to be k-L(2, 1)-choosable. The L(2, 1)-choice number λl(G) of a graph G is the smallest number k such that G is k-L(2, 1)-choosable. In this paper, we provide a lower bound on λl for the Cartesian products of a path and a spider. Also we provide an upper bound on λl for the Cartesian products of K^sub 2^ and a spider. The L(2, 1)-choice number of spider is determined.
Original languageEnglish
Pages (from-to)219-231
JournalJournal of Combinatorics and Number Theory
Volume6
Issue number3
Publication statusPublished - 2014

User-Defined Keywords

  • L(2, 1)-labeling
  • choosability
  • Cartesian products
  • path
  • spider

Fingerprint

Dive into the research topics of 'Bounds on L(2,1)-choice number of Cartesian products of paths and spiders'. Together they form a unique fingerprint.

Cite this