Peeling Circle Graphs: Iterative Partial Coloring with Explicit Constants

A circle graph has one vertex per chord of a circle, with two vertices adjacent when their chords cross. These graphs can have huge maximum degree while containing only small cliques, meaning groups of pairwise-crossing chords. It is known that they can nonetheless be colored with few colors. Davies and McCarty proved that every circle graph with largest clique size $\omega$ can be colored with $7\omega^2$ colors, and they flag the constant 7 as loose. Their argument is structural and gives no efficient, scalable procedure. This note proposes to obtain such a coloring by iterative partial coloring, the strategy behind the nibble method and constructive discrepancy. The algorithm proceeds in cautious rounds, coloring only part of the remaining chords each time, and it is guided by a potential function chosen so that the number of rounds, and therefore the leading constant, can be bounded explicitly.

Each round would select a set of chords that splits into non-interacting "permutation pieces". A permutation piece is a subgraph whose chords all pass near a common point. Such pieces are perfect, so they can be colored with exactly $\omega$ colors. The round colors all its pieces from one fresh block of $\omega$ colors, and the next round is chosen to lower a measure of how much large-clique structure remains. The coloring uses $\omega$ times the number of rounds, so the whole problem becomes bounding rounds per unit of clique number. We pair the upper-bound algorithm with solver-certified lower bounds on small instances. The result would be the first measured picture of what the constant is for the values of $\omega$ that actually occur in practice.

Core Claim

Coloring circle graphs from their chord (interval-overlap) representation by repeated rounds of disjoint permutation pieces gives three things at once. It is an algorithm that runs in near-linear time in the number of chords, never building the possibly quadratic edge set. It has a leading constant that a potential argument can bound, with the target of beating 7. And it has a finite-$\omega$ empirical constant that can be checked against exact chromatic numbers. The new element is not the decomposition into permutation graphs, which is the pillar technique of Davies and McCarty. It is choosing those pieces adaptively, round by round, under a potential, so that the constant comes from an explicit per-round progress inequality rather than from a fixed seven-way case analysis.

Why the obvious combination is the wrong one

The intersection of these directions suggests an obvious first idea, which the research file lists as its first gap: carry palette sparsification over to circle graphs. In palette sparsification, each vertex samples a short random list of colors and the graph is then colored from those lists, as in Alon and Assadi's work on triangle-free graphs and the asymmetric variant of Assadi and Yazdanyar. Here each chord would sample a short list from a palette of size $C\omega^2$. We think this idea fails at a basic level, and the reason shapes our proposal.

The complete bipartite graph $K_{n,n}$ is a permutation graph, hence a circle graph, with $\omega = 2$. Suppose every vertex samples $s$ colors from a palette of $k$ colors, and $k$ and $s$ stay fixed while $n$ grows. Then every $s$-subset of the palette eventually shows up as a list on both sides. A proper list coloring needs the palette split into the colors used on the left and the colors used on the right. Neither part may contain a whole list, so each part has at most $s-1$ colors. This forces $k \le 2s-2$, so the lists must hold about half the palette and sparsification saves only a factor of two.

Circle graphs are therefore not list-colorable with $f(\omega)$ colors, and sampling-based sparsification cannot exploit their good chromatic behavior. We keep the round structure of the nibble but drop random palette sampling. Rounds commit deterministic, structurally safe pieces. The randomness, if used at all, only breaks ties in the potential.

Research Program

The first component is the round primitive. We work in the overlap model, where chords become intervals on a line and two intervals are adjacent when they overlap without nesting. Intervals that all contain a common point $p$ induce a permutation graph, which can be colored optimally with $\omega$ colors in near-linear time. Two such stabbed families can safely share a color block when no interval of one overlaps an interval of the other. The round primitive picks a set of stabbing points and assigns intervals to them so that the families are pairwise non-overlapping. It colors them all with one block of $\omega$ colors and removes them.

This mirrors what the Ajaykrishnan et al. 3-coloring algorithm does with arc partitions. Theirs is an exact search costing $n^{O(\log n)}$ time. Ours is an approximate, polynomial peeling step.

The second component is the potential that guides rounds and drives the analysis. We borrow from the deterministic discrepancy walk of Lau, Wang and Zhou. Their method replaces random partial colorings with moves chosen to keep a smoothed potential under control. In our setting the potential should be a smooth proxy for the clique number of the remaining chords. A natural candidate is a soft-max, over points of the line, of a weighted count of pairwise-crossing chords near that point.

The target statement has the form

$$\Phi(G_{t+1}) \le \Phi(G_t) - \frac{1}{r},$$

where $G_t$ is the set of uncolored chords after round $t$ and $\Phi$ is the potential, normalized so that $\Phi$ is at least the clique number. If this holds, the potential starts at about $\omega$ and drops by $1/r$ per round. That gives about $r\omega$ rounds and so at most $r\omega^2$ colors. Beating Davies and McCarty means proving $r < 7$, and the proof should also show where any remaining slack enters.

This "localize the potential, then pay a constant per round" style is the one that produced sharp constants in offset Rademacher complexity and stochastic localization for log-Sobolev. Those papers supply the method in spirit. The file also notes that such tools do not carry over to discrete settings automatically, and that warning limits how much we can promise.

The third component is the lower side. To claim a constant is good at finite $\omega$, we need instances whose chromatic number is certified. We will use gc-cdcl, a hybrid of constraint programming and SAT solving, to certify $\chi$ exactly on circle graphs with up to a few hundred chords. We will run a local search over chord diagrams that maximizes the certified ratio $\chi/\omega$ for each $\omega$ from 3 to about 8. This yields an empirical lower envelope that any algorithm's color count can be compared against. The file reports Kostochka's $\Omega(\omega\log\omega)$ lower bound, and we use it only as the asymptotic reference. We do not claim to settle the asymptotic exponent. If the true asymptotics are sharper than the file's sources indicate, the finite-$\omega$ algorithmic deliverable and the certified data remain the contribution.

Baselines

The naive reference point is greedy coloring of intervals in left-endpoint order, plus DSATUR, which colors next the vertex adjacent to the most distinct colors. Both are standard. They ignore the $\chi$-bounded structure: they can spend colors tracking degree rather than $\omega$, and the analysis of Hebrard and Katsirelos shows standalone DSATUR losing badly to structured solvers. We give greedy the same interval representation and also report its best result over 100 random orderings, matching our wall-clock time. Beating it means using strictly fewer colors on average on every instance family.

The strongest competitor for the leading constant is the Davies and McCarty pillar decomposition, implemented directly as an algorithm. It is the only method in the file with a proven $7\omega^2$ guarantee, and it uses the same permutation-piece building block, so any gain must come from adaptivity rather than better primitives. We implement it on the same representation with the same exact permutation-graph colorer. The file has no reported empirical result for this decomposition, or for any algorithm on circle-graph instances. Beating it means a lower measured ratio of colors to $\omega^2$ at every tested $\omega$, together with a proven $r<7$.

For general-purpose quality on small instances, the reference is exact or near-exact solving with gc-cdcl and the joint constraint-programming model of Goudet et al.. For context on DIMACS, the hard graph-coloring benchmark set where the file has numbers, Monte Carlo Graph Coloring reports an average ratio to the chromatic number of 1.0428 for the hybrid evolutionary algorithm HEAD and 1.0851 for nested rollout policy adaptation (NRPA) on hard instances. Goudet et al. report 112 of 188 instances solved to optimality with the joint model. These numbers are not on circle graphs and serve only to calibrate what "near-optimal" means. On circle graphs we will report colors divided by the certified $\chi$, under equal time limits.

The ablation that isolates our key ingredient is a non-adaptive version. It computes all permutation pieces up front, with no potential and no recomputation between rounds, then packs them into color blocks greedily. If this version matches the adaptive one, adaptivity is not the source of any gain. A second ablation varies the fraction of remaining chords a round may color. This tests whether the cautious pacing of the nibble matters here as it does in Dubhashi et al..

Why not just…?

Why not just use palette sparsification on circle graphs? The $K_{n,n}$ argument above shows that lists must cover about half the palette even when $\omega=2$, so sampling cannot exploit $\chi$-boundedness. We will confirm this empirically by sweeping list size $s$ against palette size $k$ on circle graphs that contain large complete bipartite subgraphs. We expect list-colorability to fail sharply as soon as $k > 2s-2$.

Why not just run DSATUR or a strong heuristic like HEAD? On small circle graphs a good heuristic may well match our color counts, and that is a real threat to any claim of practical superiority. It is not a threat to the constant-factor claim, because heuristics come with no $f(\omega)$ guarantee. The experiments separate the two questions. Certified-$\chi$ comparisons show whether heuristics are already near-optimal on small instances, and million-chord instances show whether they stay within $r\omega^2$ when the edge set is too large to build.

Why not just call an exact solver? Zykov-based solvers keep one Boolean variable per non-edge, so memory grows quadratically, as Hebrard and Katsirelos note. Even with strong reduction rules, Goudet et al. leave 76 of 188 instances unsolved. We use solvers where they are strong, to certify the lower side, rather than competing with them.

Why not just tighten the constants inside the Davies and McCarty case analysis? This is plausible and might shave the 7. The comparison with the non-adaptive ablation tests it directly: the ablation is essentially a fixed decomposition, and if it matches the adaptive algorithm, the per-round potential is unnecessary and the simpler route wins.

Proposed Experiments

Instances come from three families. The first is random chord diagrams with $n$ from $10^3$ to $10^6$ chords. The second is planted families that combine large complete bipartite pieces with nested crossing structures. The third is the adversarial small diagrams found by solver-guided search, with $n \le 300$ and certified $\chi$. On every instance we record colors used divided by $\omega^2$, colors used divided by $\chi$ where $\chi$ is certified, rounds divided by $\omega$, and wall-clock time and memory.

Four checks are decisive. First, the measured rounds per unit of $\omega$ should concentrate at a value clearly below 7 on all families, and the adversarial search should be unable to push the adaptive algorithm's color count above $r\omega^2$ for the proven $r$. Second, the adaptive algorithm should beat both the pillar baseline and its non-adaptive ablation at every $\omega$. If it does not, the potential adds nothing and we report the tightened fixed decomposition instead. Third, on million-chord instances the algorithm should run in near-linear time from the interval representation, a regime where exact solvers run out of memory. Fourth, the sparsification sweep should show the predicted failure threshold at $k > 2s-2$, recording in data why the round-based approach, not list sampling, is the right way to bring the nibble method to $\chi$-bounded classes.