Coloring, sparseness, and girth

Noga Alon, Alexandr Kostochka, Benjamin Reiniger, Douglas B. West, Xuding ZhuIsrael 2014 · arXiv

TL;DR

This paper constructs a new class of bipartite graphs with large girth that are "almost" k-choosable, meaning they require k colors even when lists are large and subgraphs are sparse. This provides a sharp counterexample to a conjecture about the relationship between average degree and choosability in bipartite graphs.

What Problem Does This Paper Address?

The field of graph coloring has a rich history, with a particular focus on "choosability." A graph is k-choosable if, for any assignment of k colors to each vertex (a "list assignment"), there's always a way to color the graph using only colors from the assigned lists, such that adjacent vertices have different colors. The "choice number" of a graph is the smallest k for which it's k-choosable.

A well-known result states that if a bipartite graph has an average degree less than k, it's k-choosable. A stronger result by Alon and Tarsi shows that if every subgraph of a bipartite graph has an average degree less than k, it's k-choosable. This suggests that an average degree of $2(k-1)$ might be a critical threshold for k-choosability in bipartite graphs. However, it was not known if this bound was sharp, meaning if there exist bipartite graphs with average degree close to $2(k-1)$ that are not k-choosable, especially those with large "girth" (the length of the shortest cycle). This paper tackles this question by constructing such graphs.

Methods

The core of the paper's construction relies on a novel type of graph called an "r-augmented tree." This is a rooted tree where each leaf is connected to $r$ of its ancestors. The authors then build "$(d, r, g)$-graphs" by taking a complete $d$-ary tree and augmenting it in a specific way to ensure a minimum girth $g$.

The construction of these $(d, r, g)$-graphs is inductive and quite intricate, involving lemmas that relate the height of these trees to their girth and augmentation parameters. The proofs for these lemmas are combinatorial and rely on carefully analyzing paths and cycles within the constructed graphs.

These $(d, r, g)$-graphs are then used as building blocks to construct bipartite graphs that are not k-choosable. The authors achieve this by carefully designing list assignments for the vertices. They show that even when lists are large and subgraphs are sparse (meaning they have average degree at most $2(k-1)$), these graphs still cannot be properly colored.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Sharpness of the $2(k-1)$ bound: The paper demonstrates that the $2(k-1)$ average degree bound for k-choosability in bipartite graphs is indeed sharp. They construct graphs that are not k-choosable despite having subgraphs with average degree at most $2(k-1)$.
  • Girth matters: The constructions are designed to have arbitrarily large girth, showing that the lack of k-choosability persists even in graphs that are "cycle-sparse."
  • r-augmented trees as building blocks: The introduction of r-augmented trees provides a flexible framework for constructing complex graphs with controlled properties like girth and bipartiteness.
  • Connection between tree height and girth: The paper reveals a surprisingly rapid growth in the height of these augmented trees as the desired girth increases, suggesting a deep connection between these parameters.

Key Results

  • Theorem 1.2: For any $g, k \in \mathbb{N}$, there exists a bipartite graph $G$ with girth at least $g$ that is not $k$-choosable, even though every proper subgraph has an average degree of at most $2(k-1)$. This is a significant result as it shows the $2(k-1)$ bound is sharp.
  • Theorem 1.3: For any $d, r, g \in \mathbb{N}$, a $(d, r, g)$-graph exists. These graphs are crucial for the construction in Theorem 1.2.
  • Theorem 3.4: A graph with girth at least $g$ that is not $k$-colorable and has a maximum average degree of at most $2(k-1)$ is constructed. This is a result for general graphs, not just bipartite ones.
  • Theorem 3.5: A bipartite graph $G_k$ is shown to be not L-colorable for a specific list assignment $L$ where adjacent lists share exactly one color, highlighting the sensitivity of choosability to list intersection sizes.

Limitations and Future Work

  • Height of trees: The paper notes that the height of the constructed $(d, r, g)$-graphs grows extremely rapidly with girth, which can be a practical limitation for explicit constructions. Future work could explore more efficient constructions or bounds on this height.
  • Complexity of constructions: While the constructions are theoretically significant, they are quite complex and inductive, making them challenging to implement directly.
  • Generalization of results: The paper focuses on bipartite graphs. Extending these results or similar constructions to general graphs with large girth and low average degree could be a future direction.
  • List assignment sharpness: The paper investigates the sharpness of list assignment conditions (e.g., size of union, intersection of lists). Further exploration into the precise conditions that guarantee L-colorability for various graph classes remains an active area.

Summary updated

Abstract

An $r$-augmented tree is a rooted tree plus $r$ edges added from each leaf to 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. Using the resulting graphs, we construct sparse non-$k$-choosable bipartite graphs, showing that maximum average degree at most $2(k-1)$ is a sharp sufficient condition for $k$-choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non-$k$-colorable graphs and hypergraphs with any girth $g$.
BibTeX
@inproceedings{alon2014coloring,
  author = {Noga Alon and Alexandr Kostochka and Benjamin Reiniger and Douglas B. West and Xuding Zhu},
  title = {{Coloring, sparseness, and girth}},
  booktitle = {Israel},
  year = {2014},
}
Figure