Independence in $K_4$-free graphs with no degree repeated more than four times

A 1995 paper of Erdős, Faudree, Reid, Schelp and Staton asked whether forbidding a clique $K_r$ while bounding how often vertex degrees may repeat forces a linear-size independent set. Writing $f(G)$ for the maximum multiplicity of a value in the degree sequence of an $n$-vertex graph $G$ (its repetition number) and $\beta(G)$ for its independence number (the size of a largest set of pairwise non-adjacent vertices), they proved that triangle-free graphs satisfy $\beta(G)\ge n/k$ whenever $f(G)\le k$, constructed $K_r$-free graphs for $r\ge5$ with $f(G)=2$ and $\beta(G)=o(n)$, and settled the $K_4$-free cases $f(G)=2$ (then $\beta(G)\ge n/12$) and $f(G)=3$ (then $\beta(G)=\Omega(n)$), leaving $f(G)\ge4$ open. Bollobás (1996) constructed $K_4$-free graphs with at most five vertices of any one degree and $\beta(G)=o(n)$, and Bollobás and Scott (1997) resolved the companion triangle-free sharpness question for every $k\ge2$. Consequently the answer is now known to be 'sublinear independence is possible' for every $k\ge5$ and 'linear independence is forced' for $k\le3$, leaving exactly one case undecided: $k=4$. The problem is to determine whether there exist arbitrarily large $K_4$-free graphs in which no degree value is attained by more than four vertices and whose independence number is $o(n)$, or whether some absolute constant $c>0$ forces $\beta(G)\ge c\,n$ for all such graphs.

Background

Two elementary observations motivate the source question. First, every finite simple graph has at least two vertices of equal degree, since the degree values $0$ and $n-1$ cannot both occur; it is therefore natural to measure how often degrees repeat. For a graph $G$ on $n$ vertices let $f(G)$ denote the maximum multiplicity of a value in the degree sequence of $G$, i.e. the largest number of vertices sharing any single degree; in later literature this parameter is called the repetition number $\mathrm{rep}(G)$. Second, let $\beta(G)$ denote the independence number (the size of a largest set of pairwise non-adjacent vertices), and call $G$ $K_r$-free if no $r$ vertices of $G$ are pairwise adjacent. Erdős, Fajtlowicz and Staton (1991) proved that a triangle-free graph ($K_3$-free) in which no degree is repeated more than twice must be bipartite, so $\beta(G)\ge n/2$. The general triangle-free phenomenon is elementary: if $f(G)\le k$ then the degree values, being distinct integers each used at most $k$ times, force the maximum degree to be at least about $n/k$, and in a triangle-free graph the neighborhood of any vertex is an independent set; Erdős, Faudree, Reid, Schelp and Staton (1995) recorded the resulting bound $\beta(G)\ge n/k$ (up to rounding) and matched it — the case $k=2$ is exact by the bipartite theorem, and they explicitly constructed triangle-free graphs $G_n$ with $f(G_n)=4$ and $\beta(G_n)\le(1/4+o(1))n$. Forbidding larger cliques reverses the picture: the same authors took two copies of a triangle-free graph of sublinear independence and joined degree-synchronized vertices across the copies, obtaining $K_r$-free graphs with $r\ge5$ that have $f(G)=2$ and $\beta(G)=o(n)$; hence no bound on degree multiplicity forces linear independence once $r\ge5$. The borderline $r=4$ is the subject of the source paper. Using ordered-degree inequalities (for the nondecreasing degree list, $d_i\ge i/k$, and $d_{i+r}-d_i\ge r/k$ when $r$ is a multiple of $k$), an induced-edge counting inequality, and the classical Ramsey–Turán bound for $K_4$-free graphs — a $K_4$-free $n$-vertex graph with $\beta(G)=o(n)$ has at most $(1/8+o(1))n^2$ edges (surveyed by Simonovits and Sós) — they proved $\beta(G)\ge n/12$ when $f(G)=2$, and $\beta(G)=\Omega(n)$ when $f(G)=3$. However, their density argument produces induced subgraphs whose edge count exactly saturates, but cannot be pushed beyond, the $(1/8+o(1))n^2$ Ramsey–Turán threshold once the multiplicity bound reaches $4$, so it cannot decide the case $f(G)\ge4$. Bollobás (1996) then constructed a sequence of $K_4$-free graphs with at most five vertices of any one degree and independence number $o(n)$, and Bollobás and Scott (1997) resolved the companion triangle-free question for every $k\ge2$ by a probabilistic construction of triangle-free graphs with no degree repeated more than $k$ times and $\beta(G)=(1+o(1))n/k$. These results settle every case of the source question except one: the multiplicity bound $k=4$ for $K_4$-free graphs.

Problem Statement

Determine the last undecided case of the Erdős–Faudree–Reid–Schelp–Staton question on $K_4$-free graphs, the degree-multiplicity bound $k=4$. Exactly one of the following two alternatives holds, and the problem is to decide which. (a) Existence: there is a sequence $(G_n)$ of $K_4$-free graphs with $|V(G_n)|\to\infty$, each having no degree value attained by more than four vertices (that is, $f(G_n)\le4$, where $f$ is the maximum multiplicity of a degree value), and with independence number $\beta(G_n)=o(|V(G_n)|)$. (b) Linear lower bound: there is an absolute constant $c>0$ such that every $K_4$-free graph $G$ with $f(G)\le4$ satisfies $\beta(G)\ge c\,|V(G)|$. Both neighboring regimes are already settled — for $f(G)\le3$ a linear lower bound holds, and for $f(G)\le5$ constructions with sublinear independence exist — so deciding this case completes the classification of how degree-multiplicity constraints interact with forbidden cliques and independence in the source question. Companion quantitative refinements (the optimal constant in the $f(G)\le3$ bound, or the exact smallest sufficient $k$ if branch (a) holds) are context and are not required for completion.

References

1. P. Erdős, R. Faudree, T. J. Reid, R. Schelp, W. Staton, Degree sequence and independence in K(4)-free graphs, Discrete Mathematics 141 (1995) 285–290. DOI: 10.1016/0012-365X(93)E0226-T, https://doi.org/10.1016/0012-365x(93)e0226-t (source paper; zbMATH Zbl 0833.05074)
2. B. Bollobás, Degree multiplicities and independent sets in K4-free graphs, Discrete Mathematics 158 (1996) 27–35. DOI: 10.1016/0012-365X(95)00002-E, https://doi.org/10.1016/0012-365X(95)00002-E (zbMATH Zbl 0858.05056)
3. B. Bollobás, A. D. Scott, Independent sets and repeated degrees, Discrete Mathematics 170 (1997) 41–49. DOI: 10.1016/0012-365X(95)00355-Z, https://doi.org/10.1016/0012-365X(95)00355-Z (zbMATH Zbl 0881.05071)
4. P. Erdős, S. Fajtlowicz, W. Staton, Degree sequences in triangle-free graphs, Discrete Mathematics 92 (1991) 85–88. DOI: 10.1016/0012-365X(91)90269-8, https://doi.org/10.1016/0012-365X(91)90269-8 (zbMATH Zbl 0752.05028)
5. Y. Caro, D. B. West, Repetition number of graphs, The Electronic Journal of Combinatorics 16 (2009) #R7. DOI: 10.37236/96, https://doi.org/10.37236/96
6. Y. Caro, A. Shapira, R. Yuster, Forcing $k$-Repetitions in Degree Sequences, The Electronic Journal of Combinatorics 21 (2014) #P1.24. DOI: 10.37236/3503, https://doi.org/10.37236/3503 (arXiv:1312.1213)
7. Y. Caro, R. Yuster, Induced subgraphs with many repeated degrees, Discrete Mathematics 343 (2020) 111828. DOI: 10.1016/j.disc.2020.111828, https://doi.org/10.1016/j.disc.2020.111828 (arXiv:1811.07221)
8. Z. Liu, Q. Zeng, Equating Three Degrees of Graphs, The Electronic Journal of Combinatorics 33 (2026) #P2.4. DOI: 10.37236/13035, https://doi.org/10.37236/13035 (arXiv:2505.00504)
9. G. Sun, J. Hou, Q. Zeng, Large induced subgraphs with three repeated degrees, Discrete Mathematics 346 (2023) 113344. DOI: 10.1016/j.disc.2023.113344, https://doi.org/10.1016/j.disc.2023.113344
10. R. J. Faudree, C. C. Rousseau, R. H. Schelp, Problems in Graph Theory from Memphis, in: The Mathematics of Paul Erdős II, Springer, New York, 2013, pp. 95–118. DOI: 10.1007/978-1-4614-7254-4_8, https://doi.org/10.1007/978-1-4614-7254-4_8
11. P. Nelson, A. J. Radcliffe, Semi-regular graphs of minimum independence number, Discrete Mathematics 275 (2004) 237–263. DOI: 10.1016/S0012-365X(03)00109-2, https://doi.org/10.1016/S0012-365X(03)00109-2
12. M. Simonovits, V. T. Sós, Ramsey–Turán theory, Discrete Mathematics 229 (2001) 293–340. DOI: 10.1016/S0012-365X(00)00214-4, https://doi.org/10.1016/S0012-365X(00)00214-4
13. Z. Liu, Q. Zeng, Large induced subgraphs with $k$ vertices of maximum degree, arXiv preprint arXiv:2609.01681 (2026), https://arxiv.org/abs/2609.01681