## 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 T_{r,s}-choice numbers where T_{r,s} = {0,s,2s,...,rs} are presented for even cycles, notably that T_{r,s}-ch(C_{2n}) = 2r + 2 if n ≥ r + 1. More bounds are obtained by applying algebraic and probabilistic techniques, such as that T-ch(C_{2n})≤2|T| if 0 ∈ T, and c_{1}r log n ≤ T_{r,s}-ch(K_{n,n}) ≤ c_{2}r log n for some absolute positive constants c_{1},c_{2}.

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