Circular chromatic index of small graphs

Imagine you are a traffic engineer trying to manage a complex intersection. You have a set of traffic lights (colors) and a bunch of roads (edges) meeting at various intersections (vertices). Your goal is to assign a light color to every road so that no two roads meeting at the same intersection flash the same color at the same time. This is the classic problem of Edge Coloring.

Usually, we use whole numbers for colors: Red (1), Blue (2), Green (3). But in this paper, the authors are playing with a more flexible version called Circular Edge Coloring.

The Big Idea: The Color Wheel

Instead of a list of colors, imagine a continuous color wheel (like a clock face).

The "Red" light isn't just one spot; it's a tiny arc.
The rule is: If two roads meet, their colors must be far enough apart on the wheel so they don't clash.
The "Circular Chromatic Index" ( $\chi'_c$ ) is essentially asking: "How big does this color wheel need to be to make the traffic flow smoothly?"

If you need a wheel of size 4, you might think you need 4 distinct colors. But with a circular wheel, you might get away with a wheel of size 3.9, or 4.5, or even 4.75. The smaller the wheel, the more efficient your system is.

The Mystery: The "Upper Gap"

For a long time, mathematicians had a hunch about a specific "gap" in efficiency.

If a graph has a maximum of $\Delta$ roads meeting at any point, you generally need a wheel of size somewhere between $\Delta$ and $\Delta + 1$ .
The "Upper Gap Conjecture" was a bet that there are no graphs that require a wheel size just slightly less than the maximum possible ( $\Delta + 1$ ). It was thought that if you need almost the maximum, you actually need the full maximum.

The authors of this paper are the detectives who busted this theory. They found graphs that do exist in that "forbidden zone," proving that the gap isn't empty after all.

The Detective Work: Hunting for Tiny Graphs

The authors didn't just guess; they went on a massive computer hunt.

The Search: They generated millions of tiny, complex road networks (graphs) with 4, 5, or 6 roads meeting at a junction.
The Tools: They used powerful computers to try and fit these networks onto wheels of different sizes. It's like trying to fit a square peg in a round hole, but the hole is a spinning wheel, and the peg is a traffic pattern.
The Challenge: As the graphs get bigger, the number of possibilities explodes. It's like trying to find a specific grain of sand on a beach that keeps growing. For graphs with 7 roads meeting at a point, the search became so hard that even supercomputers took weeks to check just a few examples.

The Discoveries: Building Infinite Families

Once they found a few "weird" graphs that defied the rules, they didn't stop there. They asked: "Can we build an infinite family of these?"

They developed a "Lego Construction Kit":

Find a weird block: They found a small, strange graph (a "seed") that had a tricky circular index.
Chain them together: They showed that if you take many copies of this seed and link them in a circle (like a chain of train cars), the whole new, bigger train still keeps that same tricky property.
The Result: They proved there are infinite families of graphs with specific, weird values like $4.75 $($ 4 + 3/4 $) or$ 5.66 $($ 5 + 2/3$).

Why Does This Matter?

You might ask, "Who cares about traffic lights on imaginary roads?"

It breaks the rules: It shows that the mathematical world is more chaotic and interesting than we thought. There are no simple "gaps" where nothing exists; the landscape is full of hidden islands.
It helps with complexity: Understanding these "edge cases" helps us understand the limits of how we can organize things. If you are designing a network (like the internet or a power grid) and you want to avoid conflicts, knowing exactly how much "buffer" you need is crucial.
The "Critical" Graphs: The authors found that some of these weird graphs are "critical." This means if you remove even one road, the whole system becomes easier to manage. These are the "weakest links" that hold the whole structure together.

The Takeaway

Think of this paper as a map of a strange new continent.

Before: Everyone thought there was a vast, empty ocean (the "gap") between the "easy" traffic patterns and the "impossible" ones.
Now: The authors have found islands in that ocean. They have built bridges to these islands and shown that there are infinite paths leading to them.

They didn't just find one weird graph; they found the recipe to build an infinite number of them, proving that the mathematical universe is full of surprises just waiting to be discovered by those willing to look closely at the smallest details.

Here is a detailed technical summary of the paper "Circular chromatic index of small graphs" by Ján Mazák and Filip Zrubák.

1. Problem Statement and Context

The paper investigates the circular chromatic index, denoted as $\chi'_c(G)$ , for finite graphs and multigraphs with maximum degree $\Delta \in \{4, 5, 6\}$ .

Definition: The circular chromatic index is the infimum of real numbers $r$ such that the graph admits a circular $r$ -edge-colouring. This generalizes the standard integer edge-colouring (chromatic index $\chi'$ ). For any graph, $\chi'(G) = \lfloor \chi'_c(G) \rfloor$ .
The "Upper Gap" Conjecture: A central open problem is the structure of the set of possible values for $\chi'_c$ . Specifically, the "Upper Gap Conjecture" posits that for an integer $k \ge 4$ , there are no graphs with $\chi'_c(G) \in [k + 1 - 1/k, k + 1]$ . In other words, there is a "gap" just below the upper bound $\Delta + 1$ where no graph values exist.
Motivation: While the lower end of the interval $[\Delta, \Delta+1]$ is well-understood (dense with rational values for $\Delta=3$ ), the upper end near $\Delta+1$ is mysterious. The authors aim to determine if graphs exist with values just below $\Delta+1$ (e.g., $\Delta + 2/3, \Delta + 3/4$ ) and to characterize the exceptions that achieve $\chi'_c = \Delta + 1$ .

2. Methodology

The authors employ a hybrid approach combining computational enumeration and theoretical construction.

Computational Methods

Graph Generation: They generated complete sets of simple graphs and multigraphs for specific orders (number of vertices) and maximum degrees using nauty and genreg.
Complexity Handling: Determining $\chi'_c$ $χ_{c}^{'}$ is NP-hard (specifically DP-complete). To manage this, they formulated the existence of a $p/q$ $p / q$ -edge-colouring as a SAT (Boolean Satisfiability) problem. They used state-of-the-art SAT solvers (like Kissat) to check for valid colourings.
- To prove $\chi'_c(G) = r$ , they must prove a colouring exists for $r$ and no colouring exists for any $p/q < r$ .
Filtering: They utilized the CVD heuristic and backtracking to filter out Class 1 graphs (where $\chi' = \Delta$ ) quickly, focusing computational resources on Class 2 graphs (where $\chi' > \Delta$ ).
Scale: The search was limited by the exponential growth of graphs. For $\Delta=4$ , they analyzed graphs up to ~18 vertices; for $\Delta=5$ and $6$, the analysis was restricted to smaller orders (approx. 10–14 vertices) due to computational intractability.

Theoretical Constructions

Lemma 1 (Regularization): A key theoretical tool allowing the construction of infinite families of regular graphs from smaller "base" graphs. If a graph $H$ has $\chi'_c(H) = \Delta+1$ , two degree-1 vertices, and specific connectivity properties, one can construct infinitely many $\Delta$ -regular, 2-edge-connected graphs with the same index.
Circulant Graphs: For $\Delta=4$ , they analyzed circulant graphs $C_{2n+1}(1, 2)$ to prove specific bounds on $\chi'_c$ .

3. Key Contributions and Results

A. Computational Data and Empirical Patterns

The authors provide extensive tables (Tables 1–9) cataloging the number of graphs/multigraphs of specific orders and the values of $\chi'_c$ found.

New Values: They identified specific rational values for $\chi'_c$ in the range $(\Delta, \Delta+1)$ , including $\Delta + 1/2, \Delta + 2/3, \Delta + 3/4$ .
Emergence Patterns:
- Specific denominators (e.g., 3, 4, 5) do not appear immediately as the graph order increases but require a threshold of vertices.
- Fractions with larger numerators tend to appear at larger orders.
- New values often appear in multigraphs before simple graphs.
Refutation of Variants: The existence of graphs with $\chi'_c$ values just below $\Delta+1$ (e.g., $5 $for$ \Delta=4 $,$ 6 $for$ \Delta=5 $) refutes edge-connectivity variants of the Upper Gap Conjecture. For instance, they found 4-connected graphs with$ \chi'_c = 5 $(where$ \Delta=4$), disproving the idea that high connectivity forces the index to drop.

B. Infinite Families of Graphs

The paper constructs several infinite families of graphs with high circular chromatic indices:

$\Delta=6$ :
- Infinitely many graphs with $\chi'_c = 6 + 2/3$ (Theorem 1).
- Infinitely many 2-connected 6-regular graphs with $\chi'_c = 7$ (Theorem 2).
$\Delta=5$ :
- Infinitely many 2-connected 5-regular graphs with $\chi'_c = 6$ (Theorem 3).
- Infinitely many multigraphs with $\chi'_c = 5 + 3/4$ (Theorem 4).
- Infinitely many 2-connected graphs with $\chi'_c = 5 + 2/3$ (Theorem 5).
$\Delta=4$ :
- Infinitely many 2-connected 4-regular graphs with $\chi'_c = 5$ (Theorem 6).
- Infinitely many multigraphs with $\chi'_c = 4 + 3/4$ (Theorem 7).
- Infinitely many 4-connected 4-regular graphs with $\chi'_c = 9/2$ (Theorem 9).

C. Theoretical Proofs for Circulants

A significant portion of the paper is dedicated to the circulant graphs $G_{2n+1} = C_{2n+1}(1, 2)$ :

Lower Bound: They proved that for any $n$ , $\chi'_c(G_{2n+1}) \ge 4.5$ (Lemma 3).
Upper Bound: They proved that for $n \ge 6$ , these graphs admit a $(9, 2)$ -edge-colouring, meaning $\chi'_c = 4.5$ (Lemma 4).
Significance: This establishes an infinite family of 4-connected, 4-regular graphs with $\chi'_c = 4.5$ , directly addressing the "Upper Gap" question for $\Delta=4$ .

D. Conjectures

Conjecture 2: For every even integer $d > 4$ , the graph obtained from $K_{d+1}$ by removing a single edge has $\chi'_c = d+1$ . (Verified computationally for $d \in \{6, 8, 10, 12\}$ ).
Problem 1: They question whether for simple graphs with $\Delta=4$ , the only values in $(4.5, 5]$ are $14/3 $and$ 5$.

4. Significance

Refutation of Conjectures: The results strongly challenge the "Upper Gap Conjecture" in its strongest forms. The existence of highly connected regular graphs with $\chi'_c$ values arbitrarily close to $\Delta+1$ (specifically $\Delta+1/2, \Delta+2/3$ , etc.) suggests the gap is not empty as previously hypothesized.
Critical Graphs: The authors highlight that many graphs with $\chi'_c = \Delta+1$ are not $\chi'_c$ -critical (their index is forced by subgraphs), making the search for "true" critical graphs difficult. However, they successfully constructed infinite families of such graphs.
Methodological Advancement: The paper demonstrates the limits and capabilities of current SAT-based methods for circular colouring, showing that while $\Delta=3$ is fully solvable, $\Delta \ge 7$ remains computationally out of reach for exhaustive searches.
Open Problems: The paper concludes with a refined list of open problems, shifting the focus from "do gaps exist?" to "what is the precise structure of the set of attainable values?" and "which denominators are possible in the upper half of the interval?"

In summary, this paper provides the most comprehensive computational and theoretical analysis of circular chromatic indices for small graphs to date, effectively mapping the landscape of values near $\Delta+1$ and providing concrete counterexamples to simplified versions of the Upper Gap Conjecture.