Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable

Zdenĕk Dvořák, Ken‐ichi KawarabayashiarXiv 2017 · DOI · arXiv

Abstract

We prove that every triangle-free graph of tree-width $t$ has chromatic number at most $\lceil(t + 3)/2\rceil$, and demonstrate that this bound is tight. The argument also establishes a connection between coloring graphs of tree-width $t$ and on-line coloring of graphs of path-width $t$.

Introduction

In graph theory, the chromatic number $\chi(G)$ represents the minimum number of colors required to label the vertices of a graph such that no two adjacent vertices share the same color. A fundamental parameter used to bound the chromatic number is tree-width ($t$), which measures how closely a graph resembles a tree.

It is a well-established result that any graph with tree-width $t$ is $t$-degenerate, meaning every subgraph contains a vertex of degree at most $t$. This property guarantees that such graphs can be colored using at most $t+1$ colors. This bound is considered tight because a complete graph (clique) on $t+1$ vertices, denoted $K_{t+1}$, has tree-width $t$ and requires exactly $t+1$ colors. However, the question arises: what happens to this bound if we exclude specific subgraphs?

While triangle-free graphs can generally have an arbitrarily large chromatic number, this paper demonstrates that for graphs with bounded tree-width, the absence of triangles (cliques of size 3) significantly reduces the required number of colors from $t+1$ to approximately $t/2$.

The On-line Coloring Connection

One of the paper's primary methodological contributions is establishing a bridge between static graph coloring and on-line coloring. The authors prove that determining the maximum chromatic number for the class of graphs with tree-width $t$ is equivalent to an on-line coloring game played on graphs of path-width $t$.

In this on-line variant, an "adversary" reveals the graph one vertex at a time according to a "nice" path decomposition. A coloring algorithm must assign a color to each vertex immediately upon its arrival, without knowledge of future vertices or edges. The authors utilize this equivalence (Lemma 5) to simplify the problem, allowing them to analyze the chromatic number through the lens of a linear, step-by-step construction process.

Proving the Tight Bound

The paper establishes two central theorems that define the relationship between tree-width and colorability in triangle-free graphs:

1. The Upper Bound (Theorem 1)

Every triangle-free graph of tree-width $t$ is $\lceil(t + 3)/2\rceil$-colorable. To prove this, the authors design a coloring algorithm that maintains a specific invariant across the "bags" of a tree decomposition. By analyzing "forbidden" colors—colors that cannot be assigned to a vertex because they would either violate the triangle-free constraint or the rules of proper coloring—they demonstrate that $\lceil(t + 3)/2\rceil$ colors are always sufficient to complete the coloring.

2. The Lower Bound and Tightness (Theorem 2)

For any $t$, there exists a triangle-free graph of tree-width $t$ that requires exactly $\lceil(t + 3)/2\rceil$ colors. The authors use an inductive adversarial construction to prove this. They show how an adversary can force an on-line coloring algorithm to use a specific number of colors by building independent sets within a single decomposition bag that "trap" the algorithm. This concept of a "$c$-forced" coloring serves as the engine for the proof, showing that the upper bound cannot be improved further.

Key Insights

  • The "Half-Plus-One" Rule: The most significant takeaway is that forbidding triangles essentially halves the color palette required for a given tree-width. For example, while a general graph of tree-width 10 might require 11 colors, a triangle-free graph of the same tree-width requires only 7.
  • Structural Efficiency: The research highlights how local constraints (no triangles) interact with global structural properties (tree-width) to limit the chromatic number.
  • Generalization to $K_k$-free graphs: The authors extend their logic to graphs that forbid larger cliques ($K_k$). They provide a recursive formula, $g(t, k)$, to estimate the lower bound of the chromatic number in these cases, showing that the "improvement" continues as the size of the forbidden clique increases.

Limitations and Future Research

Despite providing a definitive answer for triangle-free graphs, the paper identifies several open avenues for exploration:

  1. The $K_k$ Gap: While the bound is tight for $k=3$, a gap remains between the upper and lower bounds for $K_k$-free graphs where $k \ge 4$. Closing this gap remains an open problem.
  2. Higher Girth Requirements: The authors speculate whether the chromatic number bound drops even further if the graph is required to have a higher girth (e.g., forbidding squares or cycles of length 5), while maintaining the same tree-width.
  3. List Coloring: The authors note that these results do not extend to list coloring. In a list coloring setting, where each vertex has a unique set of available colors, a triangle-free graph of tree-width $t$ can still require $t+1$ colors, meaning the triangle-free constraint provides no benefit in that specific context.

Summary updated

Abstract

We prove that every triangle-free graph of tree-width t has chromatic number at most ceil((t + 3)/2), and demonstrate that this bound is tight. The argument also establishes a connection between coloring graphs of tree-width t and on-line coloring of graphs of path-width t.
BibTeX
@misc{dvorak2017triangle,
  author = {Zdenĕk Dvořák and Ken‐ichi Kawarabayashi},
  title = {{Triangle-free graphs of tree-width t are ceil((t + 3)/2)-colorable}},
  year = {2017},
  eprint = {1706.00337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.00337},
}

Loading related content...

Figure