\(T\)-choosability in graphs
type: Item
instance of: scholarly article
title: \(T\)-choosability in graphs
zbMATH Open document ID: 0890.05026
DOI: 10.1016/S0166-218X(97)00124-8
author: Noga Alon
author: Ayal Zaks
published in: Discrete Applied Mathematics
publication date: 1998-06-18T00:00:00Z
full work available at URL: dam
review text: Given a set of nonnegative integers \(T\) and a function \(S\) which assigns a set of integers \(S(v)\) to each vertex \(v\) of a graph \(G\), an \(S\)-list \(T\)-coloring \(c\) of \(G\) is a vertex-coloring (with positive integers) of \(G\) such that \(c(v)\in S(v)\) whenever \(v\in V(G)\) and \(|c(u)-c(w)|\notin T\) whenever \(uw\in E(G)\). For a fixed \(T\), the \(T\)-choice number \(T\text{-ch}(G)\) of a graph \(G\) is the smallest number \(k\) such that \(G\) has an \(S\)-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,\ldots ,rs\}\) are presented for even cycles, notably that \(T_{r,s} \text{-ch}(C_{2n})=2r+2\) if \(n\geq r+1\). Other bounds are obtained by applying algebraic and probabilistic techniques, such as that \(T\text{-ch}(C_{2n})\leq 2|T|\) if \(0\in T\), and \(c_{1}r \log n\leq T_{r,s} \text{-ch}(K_{n,n})\leq c_{2}r \log n\) for some absolute positive constants \(c_{1}\), \(c_{2}\). Notice that the \(T_{r,s}\)-choice numbers for even cycles were obtained independently by \textit{Barry A. Tesman} in his thesis [\(T\)-colorings, list \(T\)-colorings, and set \(T\)-colorings of graphs, Ph.D. thesis, Dept. Math., Rutgers University, New Brunswick, NJ (1989)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1139428
zbMATH Keywords: \(T\)-choosability
zbMATH Keywords: \(S\)-list \(T\)-coloring
zbMATH Keywords: vertex coloring
zbMATH Keywords: \(T\)-choice number
zbMATH Keywords: even cycle
zbMATH Keywords: complete bipartite graph
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q3142409
cites work: Colorings and orientations of graphs
cites work: Q3922703
cites work: Consistency in networks of relations
cites work: Q3993187
cites work: \(T\)-colorings of graphs: recent results and open problems
cites work: List \(T\)-colorings of graphs
cites work: Q3115277
OpenAlex ID: W2114919740
description: scientific article; zbMATH DE number 1139428