DIMACS Discrete Math/Theory of Computing Seminar


Asymptotic bounds on the choice number for sparse graphs


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


Tuesday, January 30, 1996

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.

Document last modified on January 26, 1996