# DIMACS Discrete Math/Theory of Computing Seminar

## Title:

Asymptotic bounds on the choice number for sparse graphs

## Place:

- Seminar Room 431, CoRE Building,
- Busch Campus, Rutgers University.

## Time:

- 4:30
- Tuesday, January 30, 1996

Abstract:
Consider a graph $G = (V,E)$ with
a list $S_v$ of colours prescribed to each vertex $v\in V$.
The choice number $\chi_{{}_\ell}(G)$
is the least integer $t$ such that
it is possible to find
a proper colouring $\sigma$ with $\sigma(v) \in S_v$,
whenever $|S_v| > t$ for each $v$.

In the case when $G$ is triangle free it is possible to prove that
\[ \chi_{{}_\ell}(G) = O(\Delta/\log\Delta), \]
where $\Delta$ denotes the maximum degree of $G$.
Similar bounds can be proved for other classes of graphs
satisfying local properties, e.g. $K_4$-free graphs and graphs where
each neighbourhood has low chromatic number.
We present a quite general
probabilistic method --- a variant of the well-known
``nibble method'' --- which can be used to attack these and similar
problems.

dimacs-www@dimacs.rutgers.edu
Document last modified on January 26, 1996