Coloring, Sparseness, and Girth

Douglas West
Zhejiang Normal University and University of Illinois (China and USA)



Content: A {\it proper coloring} of a graph $G$ assigns colors to its vertices so that adjacent vertices receive distinct colors. The {\it chromatic number} of $G$ is the least $k$ such that $G$ has a proper coloring from a set of $k$ colors. A {\it list assignment} $L$ on $G$ assigns a list $L(v)$ of available colors to each vertex $v$. An {\it $L$-coloring} is a proper coloring with the color on each vertex chosen from its list. A graph is {\it $k$-choosable} if it is $L$-colorable whenever each list in the assignment $L$ has size at least $k$. The lists could be identical, so the least $k$ such that $G$ is $k$-choosable is at least the chromatic number. We construct existence and sharpness examples for several questions in coloring and list coloring, using sparse graphs constructed from very tall trees. An {\it $r$-augmented tree} consists of a rooted tree plus edges added from each leaf to $r$ ancestors. For $d,g,r\in\mathbb{N}$, we construct a bipartite $r$-augmented complete $d$-ary tree having girth at least $g$. The height of such trees must grow extremely rapidly in terms of the girth. Applications of this construction involve expanding the leaves of an $r$-augmented tree into special graphs. We use it for the following: (1) A new simple construction of graphs (and uniform hypergraphs) with large girth and chromatic number. (2) Construction of bipartite graphs with large girth that are not $k$-choosable even though all proper subgraphs have average degree at most $2(k-1)$ (maximum average degree at most $2(k-1)$ makes a bipartite graph $k$-choosable). (3) Construction of a bipartite graph with large girth having a $k$-uniform list assignment $L$ from which no proper coloring can be chosen even though the lists at adjacent vertices have only one common element (having two common elements guarantees $L$-colorability). (4) Enhancement of (2) so that the union of the lists has size $2k-1$ (size at most $2k-2$ guarantees $L$-colorability). These results are joint work with Noga Alon, Alexandr V. Kostochka, Benjamin Reiniger, and Xuding Zhu.

Back to all abstracts