MATHEMATICS
Fractional coloring after the triangle-free degeneracy breakthrough
Martinsson’s 2025 result resolves a fractional coloring conjecture for triangle-free graphs. An explicit five-cycle explains the crucial relaxation.
Research checked
Newest cited publication
K7 contains many triangles, illustrating the configurations excluded in triangle-free coloring problems. The new bounds concern the restricted graph class explained in the text.
David Benbennick / Wikimedia Commons. Wikimedia-generated PNG rendering of the SVG; no editorial changes. · Image source · Public domain (released by the creator)
A graph can have no triangles and still resist a small coloring. Removing the smallest obvious source of conflict does not make every scheduling problem simple. In a preprint submitted on January 30, 2025, Anders Martinsson proved a conjecture about a more flexible kind of coloring: distribute weight across conflict-free vertex sets instead of assigning one permanent color to every vertex. The resulting bound depends on degeneracy, a measure of sparsity that can be much smaller than maximum degree. The result is striking precisely because the same improvement cannot simply be demanded of ordinary coloring.
A logarithmic saving, stated carefully
Martinsson proves that a triangle-free d-degenerate graph has fractional chromatic number at most (4 plus a term tending to zero) times d divided by ln d, as d grows. This settles the order-of-growth conjecture associated with David Harris. The natural logarithm and asymptotic qualification belong in the statement. Substituting d equal to one would make the displayed expression meaningless, and ignoring the vanishing term would convert an asymptotic theorem into an unjustified exact numerical estimate.
A graph is d-degenerate when every nonempty subgraph has some vertex with at most d neighbors inside that subgraph. Equivalently, repeatedly removing an available low-degree vertex eventually removes everything. Reversing this removal order supports a greedy coloring using at most d plus one colors. The definition controls an elimination process across all subgraphs; it is not a promise that every vertex in the original graph has degree at most d. That distinction is why a degeneracy result can reach graphs with exceptionally busy vertices.
Maximum degree and degeneracy tell different stories
Consider a star with one central vertex and one thousand leaves. Its maximum degree is one thousand, but its degeneracy is one: every nonempty subgraph has a leaf or consists of an isolated vertex. It has an ordinary two-coloring, with the center in one class and all leaves in the other. Any proposed theorem that treats this star as intrinsically thousand-color difficulty is using a coarse parameter. The example is deliberately elementary because it isolates the advantage of controlling an elimination order.
Now compare the star with a complete bipartite graph having one hundred vertices on each side. Every vertex has degree one hundred, and the graph has degeneracy one hundred because the whole graph already has that minimum degree. Nevertheless, it still uses only two colors. Thus degeneracy gives an upper-bound parameter, not a prediction of the exact chromatic number of each graph. The new theorem constrains the hardest triangle-free examples at a given degeneracy; it does not say that every such graph requires about d divided by ln d fractional colors.
The five-cycle makes fractional coloring concrete
Place five vertices around a pentagon and connect consecutive vertices. This graph has no triangle. It requires three ordinary colors: alternating two colors around an odd cycle produces a conflict at the final edge. Its largest independent sets have two vertices. For a fractional coloring, assign weight one half to each of the five nonadjacent vertex pairs. Every vertex belongs to two of those pairs and therefore receives total coverage one, while the total weight paid is five halves.
That construction is optimal. If independent sets carry nonnegative weights and cover all five vertices by at least one unit each, their total covered vertex-weight is at least five. Every independent set covers at most two vertices per unit of its own weight. Therefore twice the total weight is at least five. The upper and lower bounds match at two and a half. This complete calculation shows what the fractional relaxation changes: overlapping compatible groups can share the job even when no partition into two compatible groups exists.
A probability distribution expresses fair coverage
The same five-cycle example can be described probabilistically. Choose one of its five nonadjacent pairs uniformly at random. Every vertex is selected with probability two fifths. Multiplying those probabilities by five halves gives unit fractional coverage. More generally, if a distribution on independent sets includes every vertex with probability at least one divided by k, it produces a fractional coloring costing at most k. This is an existence statement about coordinated randomness; choosing vertices independently would usually introduce conflicting adjacent selections.
Martinsson and Raphael Steiner's distinct paper, Random independent sets in triangle-free graphs, published online in September 2025, studies distributions with vertex-specific inclusion guarantees. Its local viewpoint asks for suitable probabilities at every vertex rather than merely a large expected total independent-set size. These are different demands. A distribution can have excellent expected size while repeatedly excluding one inconvenient vertex. Fractional coloring needs coverage everywhere, so the distribution's worst-served vertices matter as much as its average performance.
Local freedom does not imply global independence
In a triangle-free graph, the neighbors of any single vertex form an independent set. Otherwise, two adjacent neighbors and the original vertex would make a triangle. This gives useful local freedom: once a vertex is held aside, several of its neighbors can coexist. But neighborhoods of different vertices overlap, and choices made around one vertex can constrain another. The pentagon already shows this tension. Every neighborhood is harmless by itself, yet the whole graph cannot be partitioned into two independent classes.
The difficulty in improving a greedy bound is to turn that local freedom into simultaneous coverage guarantees. Treating all neighborhoods as independent random experiments would discard the shared vertices and longer cycles that couple them. This is why a logarithm in an extremal estimate often signals a careful balance between selection opportunities and accumulated exclusions. That interpretation is mathematical intuition rather than a reproduction of the proof. The theorem's actual content is a rigorously justified distribution, with a guarantee that survives all those dependencies.
The earlier question had a sharper target than ordinary coloring
Harris's paper on chromatic number and triangle count, first posted in April 2016 and later published in SIAM Journal on Discrete Mathematics, investigated bounds interpolating between triangle-free and less sparse settings. It identified a fractional coloring question involving degeneracy as a way to close a remaining gap. The new result resolves that specific fractional question. Reading the older work alongside the new one makes clear why replacing maximum degree by degeneracy was substantive, and why dropping the word fractional would misreport the advance.
There is also a useful optimization perspective. Ordinary coloring selects a partition, while fractional coloring chooses a weighted collection of independent sets. The second feasible space contains the first, so its optimum can only be smaller. An improved bound in the larger space does not automatically produce a comparably good integral partition. Rounding can introduce a gap. Any practical use that needs fixed, indivisible time slots must either accept time-sharing or supply an additional rounding argument; the existence of fractional coverage alone does not complete that engineering step.
What to ask after the order of growth is settled
The established scale leaves room to understand constants, sharper local versions and effective ways to produce good fractional colorings. A statement of existence should also be distinguished from an implementation benchmark: neither a faster scheduling service nor a measured real-world improvement follows from the asymptotic inequality alone. For small degeneracy, direct combinatorial reasoning can be more informative than substituting numbers into a large-d expression. The star and pentagon are useful reminders that exact examples and worst-case asymptotics answer different questions.
The broader lesson is methodological. Sparsity is not one number, and flexibility is not one notion. Maximum degree measures the busiest vertex, degeneracy measures how a network can be dismantled, ordinary coloring demands a partition, and fractional coloring permits shared coverage. The 2025 breakthrough succeeds at a particular intersection of those choices. Keeping all four definitions visible lets readers appreciate a substantial logarithmic improvement without expecting it to solve a stronger coloring problem that the theorem never claimed to address.
Sources & further reading
Primary papers, project documentation, and research releases used in this article. Publication dates below refer to the sources themselves.
- Triangle-free d-degenerate graphs have small fractional chromatic numberarXivPublished Checked
- Random independent sets in triangle-free graphsCambridge University PressPublished Checked
- Some results on chromatic number as a function of triangle countarXivPublished Checked
FOLLOW THE QUESTION
Explore mathematics