Abstract
For decades, the relationship between the clique number ($\omega$) and the chromatic number ($\chi$) of circle graphs was known to be bounded, but the best-known upper bounds were exponential. This paper presents a significant advancement in structural graph theory by proving that circle graphs are quadratically $\chi$-bounded. Specifically, we show that $\chi \le 7\omega^2$, providing the first polynomial bound for this class.
Introduction
In the study of graph coloring, a class of graphs is considered $\chi$-bounded if the chromatic number of its members can be restricted by a function of their maximum clique size. While perfect graphs exhibit the property where $\chi = \omega$, many complex graph classes do not. Circle graphs—defined as the intersection graphs of chords in a circle—have been recognized as $\chi$-bounded since the 1980s. However, until recently, the established bound was $f(\omega) = 2^\omega$. This research bridges a long-standing gap by demonstrating that the growth of $\chi$ relative to $\omega$ is polynomial rather than exponential.
Theoretical Framework
The complexity of a graph is often characterized by two primary metrics:
- Clique Number ($\omega$): The size of the largest group of vertices where every vertex is connected to every other vertex.
- Chromatic Number ($\chi$): The minimum number of colors required to color the vertices such that no two adjacent vertices share the same color.
For circle graphs, the intersection of chords creates dependencies that make coloring non-trivial. To analyze these dependencies, the authors utilize an equivalent representation: the interval system. In this model, the circle graph is viewed as an "overlap graph" of intervals on a real line. Two vertices are adjacent if their corresponding intervals overlap but neither contains the other.
Methodology: Pillar Assignment and Partitioning
The breakthrough in this paper stems from a novel partitioning strategy. The authors demonstrate that the vertex set of any circle graph can be decomposed into at most $7\omega$ subsets. Each of these subsets induces a permutation graph.
Permutation graphs are a subclass of perfect graphs, meaning their chromatic number is equal to their clique number ($\chi = \omega$). By reducing the circle graph into a collection of permutation graphs, the problem of coloring the entire graph is transformed into coloring these $7\omega$ components, each requiring at most $\omega$ colors.
The Pillar Technique
The core mechanism for this decomposition is the "pillar assignment" method. The authors define "pillars" as specific points on the line. They prove that if a set of intervals all contain a specific pillar, the resulting overlap graph is a permutation graph. By establishing a total ordering and a sophisticated assignment rule, the authors ensure that intervals are distributed among $7\omega$ pillars such that the structural properties required for permutation graphs are maintained across the partition.
Key Results
The primary contributions of this work are summarized in the following theorems:
- Theorem 1: For any circle graph with clique number $\omega$, the chromatic number $\chi$ satisfies $\chi \le 7\omega^2$.
- Theorem 2: The vertex set of a circle graph can be partitioned into at most $7\omega$ sets, each of which induces a permutation graph.
- Corollary 3: This quadratic bound extends to polygon circle graphs (intersection graphs of polygons inscribed in a circle), yielding a polynomial bound of $\chi \le 7\omega^4$.
For a clique size of $\omega = 10$, the previous exponential bound suggested a theoretical limit of $\chi \le 1,024$. The new quadratic bound reduces this limit to 700, with the improvement becoming exponentially more pronounced as $\omega$ increases.
Discussion and Future Work
While the transition from exponential to polynomial bounds is a major milestone, the results suggest further avenues for optimization. Currently, a gap exists between the lower bound of $\Omega(\omega \log \omega)$ established by Kostochka and the $O(\omega^2)$ upper bound proven here.
The authors note that the constant factor of 7 is likely not optimal for large values of $\omega$. Furthermore, achieving a linear bound—or one closer to the logarithmic lower bound—will likely require structural insights beyond the current pillar assignment methodology. Nonetheless, this work provides the foundational framework for polynomial $\chi$-boundedness in intersection graphs.
Summary updated