The order function $F(n)$: smallest triangle-free graphs with chromatic number $n$ and no degree repeated more than three times (Erdős–Fajtlowicz–Staton)

For a finite simple graph $G$, let $f(G)$ be the maximum multiplicity of a value in the degree sequence of $G$, i.e. the largest number of vertices of equal degree (in later literature also called the repetition number). Erdős, Fajtlowicz and Staton (1991), studying Conjecture 67 of the automated conjecture-program Graffiti, proved that every triangle-free graph with $f(G)\le 2$ is bipartite, and constructed triangle-free graphs with $f(G)=3$ and unbounded chromatic number, refuting the conjecture. They introduced $F(n)$, the minimum number of vertices of a triangle-free graph with chromatic number $n$ and $f(G)=3$, determined $F(3)=7$, and exhibited a 19-vertex triangle-free 4-chromatic graph with $f(G)=3$, giving $F(4)\le 19$. No later work addressing $F(n)$ is known: the subsequent repeated-degrees literature treats only adjacent questions (independence numbers, girth-5 analogues, forcing repeated degrees by vertex deletions), so the exact value of $F(4)$ — known only to lie in $[11,19]$ — and the growth rate of $F(n)$ remain open. The problem asks to determine $F(n)$: at minimum the exact value of $F(4)$, and in full the correct order of growth of $F(n)$, in particular whether $F(n)$ is polynomial in $n$ or must grow faster, replacing the enormously large graphs produced by the 1991 embedding construction.

Background

All graphs are finite and simple. A graph is triangle-free if no three of its vertices are pairwise adjacent. The chromatic number $\chi(G)$ is the least number of colors needed to color the vertices so that adjacent vertices receive different colors. The degree sequence of $G$ lists the numbers of neighbors of its vertices; $f(G)$ denotes the maximum multiplicity of a value in this sequence — the largest number of vertices sharing a single degree — called the repetition number $\mathrm{rep}(G)$ in the later literature. In every graph with at least two vertices some two vertices have equal degrees, so small values of $f(G)$ express the informal requirement that the degree sequence be 'spread out'.

Graffiti, a computer program of Siemion Fajtlowicz that generates conjectures in graph theory (its published description is [2]), posed in its 1987 conjecture list 'Written on the wall' [3] the conjecture (No. 67) that every triangle-free graph satisfies $\chi(G)\le f(G)$. Erdős, Fajtlowicz and Staton [1] tested this conjecture and proved three things. First, every triangle-free graph with $f(G)\le 2$ is bipartite, so the conjecture holds comfortably in that regime. Second, an embedding theorem: every triangle-free graph is an induced subgraph of a triangle-free graph with $f=3$; since triangle-free graphs of arbitrarily large chromatic number exist, this yields triangle-free graphs with $f=3$ and unbounded chromatic number and refutes Conjecture 67. Third, they introduced the function $F(n)$, the minimum order (number of vertices) of a triangle-free graph with $\chi(G)=n$ and $f(G)=3$, determined $F(3)=7$, and gave an explicit 19-vertex triangle-free graph with $\chi=4$ and $f=3$, so $F(4)\le 19$; they described it as the smallest counterexample known to them and left the exact value of $F(4)$ and the behavior of $F(n)$ for $n\ge 5$ open. A useful scope remark: by the first theorem, every triangle-free graph with $\chi\ge 3$ has $f\ge 3$, so the readings '$f(G)=3$' and '$f(G)\le 3$' delimit the same class of graphs in the range relevant to $F(n)$.

Classical minima for triangle-free graphs with prescribed chromatic number give lower bounds on $F(n)$ without using the multiplicity constraint: the 5-cycle is the smallest 3-chromatic triangle-free graph; the Grötzsch graph — an 11-vertex 4-chromatic triangle-free graph obtained from the 5-cycle by Mycielski's construction, the standard operation that raises the chromatic number by one while preserving triangle-freeness — is the smallest 4-chromatic triangle-free graph, so $F(4)\ge 11$; and a computer search of Jensen and Royle [4] established that the smallest 5-chromatic triangle-free graphs have 22 vertices, so $F(5)\ge 22$.

Several adjacent research lines must be distinguished from this problem. (i) Independence side: since a triangle-free graph with $f\le 2$ is bipartite, one of its two color classes is an independent set (a set of pairwise non-adjacent vertices) of at least half the vertices; Erdős, Faudree, Reid, Schelp and Staton [5] asked whether $K_r$-free graphs (graphs containing no copy of the complete graph $K_r$ on $r$ vertices) with few repeated degrees can have independence number $\alpha(G)$ — the largest size of an independent set — equal to $o(n)$, settling $r=3$ and $r\ge 5$ and giving partial results for $r=4$; Bollobás [6] constructed $K_4$-free graphs with at most five vertices of any one degree and $\alpha(G)=o(n)$; Bollobás and Scott [7] proved probabilistically that for every $k\ge 2$ there are triangle-free $n$-vertex graphs with no degree repeated more than $k$ times and $\alpha(G)=(1+o(1))\,n/k$, the ratio asked for in [5]. For $k=3$ the resulting graphs have $\alpha\approx n/3$, which only forces $\chi\ge 3$ (always $\chi(G)\ge |V(G)|/\alpha(G)$), so this line says nothing about $F(n)$. (ii) Higher girth: Caro [8] proved Graffiti's Conjecture 119 — graphs of girth (the length of a shortest cycle) at least 5 satisfy $\chi(G)\le f(G)$ — for graphs with at least $e^{49}$ vertices; hence any counterexample with $f=3$ on at least $e^{49}$ vertices must contain a 4-cycle, which isolates the triangle-free (girth-4) regime of the present problem as the critical open case, but does not touch it. (iii) The repetition-number program: Caro and West [9] studied the minimum repetition number of graphs in various classes, and Caro, Shapira and Yuster [10], Kogan [13], Sun, Hou and Zeng [14], and Liu and Zeng [15] developed the theme of forcing repeated degrees by deleting few vertices (the final paper closes the problem $C(3)=3$: every graph with at least 5 vertices admits a set of at most 3 vertices whose deletion leaves three vertices of equal degree). None of these works constrains the chromatic number of bounded-repetition triangle-free graphs. (iv) A different question attributed to the same 1991 paper (recorded in the book of Chung and Graham [12] on Erdős's graph problems and studied by Caro and Yuster [11]) concerns the least order of a graph guaranteed to contain a large induced regular subgraph; it remains open and is unrelated to the function $F(n)$ studied here.

Problem Statement

For an integer $n\ge 3$, define

$$F(n)=\min\{|V(G)|:\ G\ \text{triangle-free},\ \chi(G)=n,\ f(G)=3\},$$

where $\chi(G)$ is the chromatic number of $G$ and $f(G)$ is the maximum multiplicity of a value in the degree sequence of $G$ (the largest number of vertices of equal degree). The constraint $f(G)=3$ may equivalently be read as $f(G)\le 3$: every triangle-free graph with $f(G)\le 2$ is bipartite [1], so any triangle-free graph with $\chi\ge 3$ automatically has $f\ge 3$, and the two readings delimit the same class in the range relevant to $F(n)$. That $F(n)$ is finite for every $n$ follows from the construction of [1], which produces triangle-free graphs with $f=3$ of prescribed chromatic number, though of enormous order.

Determine the function $F$. The single objective — how small a triangle-free graph of chromatic number $n$ can be when no degree value may occur more than three times — has two complementary ends:

(1) Finite end. Determine the exact value of $F(4)$, currently known only to satisfy $11\le F(4)\le 19$ (lower bound: the Grötzsch graph is the smallest 4-chromatic triangle-free graph; upper bound: the explicit 19-vertex example of [1]). Determining $F(4)$ requires a triangle-free graph with $\chi=4$ and $f\le 3$ on $F(4)$ vertices together with a proof that no smaller triangle-free graph with $\chi=4$ and $f\le 3$ exists. Determining $F(5)$ (known: $F(5)\ge 22$), or rigorously improving either bound for any fixed $n$, is a special case of the same question.

(2) Asymptotic end. Determine the correct growth rate of $F(n)$ as $n\to\infty$; the embedding construction of [1] gives finite but enormously large values. Establish matching upper and lower bounds; in particular, decide whether $F(n)$ is bounded above by a polynomial in $n$ — the 'relatively small' examples asked for in [1] — or must grow super-polynomially, and identify the order of $F(n)$ up to constants or logarithmic factors.

A complete solution of the problem determines $F(4)$ exactly and pins down the order of growth of $F(n)$ (matching upper and lower bounds).

References

1. Paul Erdős, Siemion Fajtlowicz, William Staton: 'Degree sequences in triangle-free graphs', Discrete Mathematics 92(1-3):85-88, 1991. DOI: 10.1016/0012-365X(91)90269-8; https://doi.org/10.1016/0012-365X(91)90269-8; zbMATH Zbl 0752.05028, https://zbmath.org/32451.
2. Siemion Fajtlowicz: 'On conjectures of Graffiti', Discrete Mathematics 72(1-3):113-118, 1988. DOI: 10.1016/0012-365X(88)90199-9; https://doi.org/10.1016/0012-365X(88)90199-9.
3. Siemion Fajtlowicz: 'Written on the wall' (Graffiti conjecture list), 1987 — Conjecture 67. Unpublished conjecture list; no DOI or stable public URL is known.
4. Tommy R. Jensen, Gordon F. Royle: 'Small graphs with chromatic number 5: A computer search', Journal of Graph Theory 19(1):107-116, 1995. DOI: 10.1002/jgt.3190190111; https://doi.org/10.1002/jgt.3190190111; zbMATH Zbl 0821.05023, https://zbmath.org/716432.
5. Paul Erdős, Ralph Faudree, Talmage James Reid, Richard Schelp, William Staton: 'Degree sequence and independence in K(4)-free graphs', Discrete Mathematics 141(1-3):285-290, 1995. DOI: 10.1016/0012-365X(93)E0226-T; https://doi.org/10.1016/0012-365X(93)E0226-T; zbMATH Zbl 0833.05074, https://zbmath.org/778543.
6. Béla Bollobás: 'Degree multiplicities and independent sets in K4-free graphs', Discrete Mathematics 158(1-3):27-35, 1996. DOI: 10.1016/0012-365X(95)00002-E; https://doi.org/10.1016/0012-365X(95)00002-E; zbMATH Zbl 0858.05056, https://zbmath.org/943216.
7. Béla Bollobás, A. D. Scott: 'Independent sets and repeated degrees', Discrete Mathematics 170(1-3):41-49, 1997. DOI: 10.1016/0012-365X(95)00355-Z; https://doi.org/10.1016/0012-365X(95)00355-Z; zbMATH Zbl 0881.05071, https://zbmath.org/1047045.
8. Yair Caro: 'Colorability, frequency and Graffiti—119', Journal of Combinatorial Mathematics and Combinatorial Computing 27:129-134, 1998. zbMATH Zbl 0927.05030, https://zbmath.org/1308947.
9. Yair Caro, Douglas B. West: 'Repetition Number of Graphs', The Electronic Journal of Combinatorics 16(1):#R7, 2009. DOI: 10.37236/96; https://doi.org/10.37236/96; article page https://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r7.
10. Yair Caro, Asaf Shapira, Raphael Yuster: 'Forcing $k$-Repetitions in Degree Sequences', The Electronic Journal of Combinatorics 21(1):#P1.24, 2014. DOI: 10.37236/3503; https://doi.org/10.37236/3503; article page https://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p24.
11. Yair Caro, Raphael Yuster: 'Induced subgraphs with many repeated degrees', Discrete Mathematics 343(5):111828, 2020. DOI: 10.1016/j.disc.2020.111828; https://doi.org/10.1016/j.disc.2020.111828; preprint arXiv:1811.07221, https://arxiv.org/abs/1811.07221.
12. Fan Chung, Ron Graham: 'Erdős on graphs. His legacy of unsolved problems', A K Peters, Wellesley, MA, 1998 (xiii+142 pages). zbMATH https://zbmath.org/1131467.
13. Shimon Kogan: 'A note on forcing 3-repetitions in degree sequences', Discussiones Mathematicae Graph Theory 43(2):457-462, 2023. DOI: 10.7151/dmgt.2376; https://doi.org/10.7151/dmgt.2376.
14. Gaoxing Sun, Jianfeng Hou, Qinghou Zeng: 'Large induced subgraphs with three repeated degrees', Discrete Mathematics 346(5):113344, 2023. DOI: 10.1016/j.disc.2023.113344; https://doi.org/10.1016/j.disc.2023.113344.
15. Zhen Liu, Qinghou Zeng: 'Equating three degrees of graphs', preprint arXiv:2505.00504, 2025. https://arxiv.org/abs/2505.00504.