Abstract
Given a set of nonnegative integers T. and a function ℒ which assigns a set of integers S(v) to each vertex v of a graph G, an ℒ-list T-coloring c of G is a vertex-coloring (with positive integers) of G such that c(v) ∈ S(v) whenever v ∈ V(G) and |c(u) - c(w)| ∉ T whenever (u,w) ∈ E(G). For a fixed T, the T-choice number T-ch(G) of a graph G is the smallest number A such that G has an ℒ-list T-coloring for every collection of sets S(v) of size k each. Exact values and bounds on the Tr,s-choice numbers where Tr,s = {0,s,2s,...,rs} are presented for even cycles, notably that Tr,s-ch(C2n) = 2r + 2 if n ≥ r + 1. More bounds are obtained by applying algebraic and probabilistic techniques, such as that T-ch(C2n)≤2|T| if 0 ∈ T, and c1r log n ≤ Tr,s-ch(Kn,n) ≤ c2r log n for some absolute positive constants c1,c2.
Original language | English (US) |
---|---|
Pages (from-to) | 1-13 |
Number of pages | 13 |
Journal | Discrete Applied Mathematics |
Volume | 82 |
Issue number | 1-3 |
DOIs | |
State | Published - Mar 2 1998 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics