Coloring small locally sparse degenerate graphs and related problems

Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang · 2026

Read Coloring small locally sparse degenerate graphs and related problems by Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15245.txt.

Introduction

Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, and Shengtong Zhang sharpen a classic coloring bound. Their 2026 arXiv paper deals with degenerate graphs, where every part has a low-degree vertex. A d-degenerate graph can always be colored with d plus one colors.

Complete graphs show that this bound cannot be improved in general. The authors ask if it stays tight under extra limits. They study small, locally sparse degenerate graphs, where large cliques are forbidden. Related problems get the same treatment, to see where the classic bound can finally be beaten.

Catalog record

CREATORDomagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-15245

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coloring small locally sparse degenerate graphs and related problems Thanks: The second author gratefully acknowledges funding from NSF awards DMS-2452737 and DMS-2154129. Thanks: The third author gratefully acknowledges funding from the SNSF Ambizione Grant No. 216071. Thanks: The fourth author gratefully acknowledges funding from the SNSF Grant 200021-228014. Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, Shengtong Zhang Abstract . The classic upper bound on the chromatic number of d d -degenerate graphs is d + 1 d+1 , shown to be tight by complete graphs. A natural question is whether this bound remains tight if further constraints are imposed on the graph, such as forbidding large cliques. Quite surprisingly, classic constructions of Tutte and Zykov from the early 50s and a generalization due to Kostochka and Nešetřil from 1999 show that there exist d d -degenerate ( d + 1 ) (d+1) -chromatic graphs that are triangle-free (and even have large girth). However, the orders of all known constructions of d d -degenerate ( d + 1 ) (d+1) -chromatic graphs with small clique number grow rapidly with d d . Motivated by this phenomenon and addressing a problem posed by the second author at the Oberwolfach Graph Theory workshop, we prove that the minimum order f ⁡ ( d ) f(d) of a d d -degenerate triangle-free graph of chromatic number d + 1 d+1 grows exponentially in a polynomial of d d , concretely e Ω ⁡ ( d ) ≤ f ⁡ ( d ) ≤ e O ⁡ ( d 2 ​ log ⁡ d ) . e^{\Omega(d)}\leq f(d)\leq e^{O(d^{2}\log d)}. The lower bound follows from a novel upper bound on the chromatic number of triangle-free graphs that may be of independent interest: Every triangle-free d d -degenerate graph G G on n ≤ e O ⁡ ( d ) n\leq e^{O(d)} vertices satisfies χ ⁡ ( G ) ≤ O ⁡ ( d log ⁡ ( d / log ⁡ n ) ) . \chi(G)\leq O\left(\frac{d}{\log\left(d/\log n\right)}\right). We also extend this to a more general result about degenerate graphs with sparse neighborhoods, which has applications to a variety of graph coloring problems: For example, we prove that every counterexample to Hadwiger’s conjecture with parameter t t must have a complete bipartite subgraph with one exponentially large side ( K a , b K_{a,b} where a = ( log ⁡ t ) 1 / 2 − o ⁡ ( 1 ) a=(\log t)^{1/2-o(1)} and b = e t 1 − o ⁡ ( 1 ) b=e^{t^{1-o(1)}} ) or a small and very dense subgraph (of order ≤ t \leq t with ≥ t 2 − o ⁡ ( 1 ) \geq t^{2-o(1)} edges) in some neighborhood. For the upper bound on f ⁡ ( d ) f(d) we establish a surprising connection between f ⁡ ( d ) f(d) and the on-line-chromatic number g ⁡ ( n ) g(n) of n n -vertex triangle-free graphs. We also give an asymptotic improvement of the previous best upper bound for g ⁡ ( n ) g(n) due to Lovász, Saks and Trotter from 1989. Along the way, we disprove a generalization of Harris’ conjecture on fractional coloring to graphs of bounded clique number and raise numerous problems which open up various interesting directions to explore for future research. 1. Introduction The chromatic number \chi(G) of a graph G is one of the most important graph parameters and has been actively studied for about a century, see [ 32 ] for a recent survey. Despite this, we still do not fully understand what makes the chromatic number of a graph large, as illustrated by the fact that it is \mathsf{NP} -hard to compute \chi(G) [ 20 ] and even intractable to approximate it to within a factor n^{1-\varepsilon} for any \varepsilon>0 , where n is the order of the graph [ 10 ] . Consequently, to bound the chromatic number of a given graph, one often has to resort to one of a few known bounds that are easy to compute, such as the maximum degree or the degeneracy of the graph. Recall that a graph G is called d -degenerate for some d\in\mathbb{R}_{\geq 0} if its vertex set can be linearly ordered as v_{1},\ldots,v_{n} such that for each i\in\{1,\ldots,n\} , vertex v_{i} has at most d neighbors among the previous vertices \{v_{1},\ldots,v_{i-1}\} in the ordering. Greedy coloring along this ordering shows that \chi(G)\leq d+1 for every d -degenerate graph, which is an improvement of the weaker bound \chi(G)\leq\Delta+1 in terms of the maximum degree \Delta of the graph. Both of these bounds are tight, as evidenced by the complete graphs K_{d+1} and K_{\Delta+1} . But what if we forbid large complete subgraphs? Can we then improve these upper bounds? A seminal result of Johansson [ 18 , 19 ] states that indeed a significant saving can be obtained when considering the maximum degree. Namely, a graph of maximum degree \Delta has chromatic number at most O\left(\frac{\Delta}{\log\Delta}\right) if it is triangle-free and at most O_{r}\left(\frac{\Delta\log\log\Delta}{\log\Delta}\right) if it is K_{r} -free for r\geq 4 ; see also Molloy [ 27 ] for improved constants. However, quite surprisingly, when moving from maximum degree to degeneracy, such a saving is no longer possible: Already in the early 50s, Zykov [ 37 ] and Tutte [ 5 ] published constructions which show that for every d\in\mathbb{N} , there exists a triangle-free d -degenerate graph of chromatic number d+1 , so even forbidding triangles does not achieve any improvement of the degeneracy bound. As shown by Kostochka and Nešetřil [ 22 ] in 1999, one can modify Tutte’s construction to even obtain d -degenerate (d+1) -chromatic graphs of large girth. This may seem like a conclusive answer to our above question, but this is not quite the case. Indeed, one can check that the number of vertices of the d -degenerate graphs constructed by Zykov and Tutte grows extremely rapidly (much faster than exponential in d ). It is thus natural to ask whether this property of the constructions is a necessary one: If a triangle-free d -degenerate graph has not too many vertices, can we then improve the upper bound d+1 on the chromatic number significantly? Moreover, if so, how fast does the smallest number of vertices f(d) of a triangle-free d -degenerate graph with chromatic number d+1 grow? These questions, which were also explicitly posed by the second author at the Oberwolfach Graph Theory Workshop in January 2025 and came from work on a generalization of Ramsey numbers [ 11 ] , are the topic of our paper. 1.1. Main results. Coloring small locally sparse degenerate graphs. Our first theorem gives a positive answer to the first question above, as follows. Theorem 1.1 . There are absolute constants c,C>0 such that the following holds. Let d\in\mathbb{R}_{\geq 1} and let G be a triangle-free d -degenerate graph on n\leq 2^{cd} vertices. Then \chi(G)\leq\frac{Cd}{\log(d/\log n)}. Alon, Krivelevich and the fourth author [ 1 ] generalized Johansson’s aforementioned result [ 18 ] on the chromatic number of triangle-free graphs with maximum degree \Delta to the more general setting of graphs with sparse neighborhoods. Namely, they showed that a graph of maximum degree \Delta in

Read the complete text