T-choosability in graphs

Noga Alon, Ayal Zaks

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalDiscrete Applied Mathematics
Volume82
Issue number1-3
DOIs
StatePublished - Mar 2 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'T-choosability in graphs'. Together they form a unique fingerprint.

Cite this