OFFSET
1,8
COMMENTS
Erdős posed the problem of calculating this sequence and conjectured that n^2/25 edges would always be sufficient. This would be sharp as the balanced blow-up of C_5 with class sizes n/5 needs at least n^2/25 edges removed to be made bipartite.
Every triangle-free graph on n vertices G, which is not bipartite, has a vertex x of degree d(x) <= 2n/5 (Andrásfai, Erdős, Sós). G\x can be made bipartite by removing a(n-1) edges. And x can be added to this coloring by removing at most d(x)/2 edges incident on x. Therefore a(n) <= a(n-1) + n/5. (Proof by Martin Fuller: see the SeqFan link.)
The value a(23)=20 is achieved by a 5-cycle with vertices blown up into independent sets of size 4,5,4,5,5 in cyclic order, plus 5 of its subgraphs. - Brendan McKay, 17 Oct 2025
LINKS
B. Andrásfai, P. Erdős, and V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Mathematics, 8 (3): 205-218, (1974).
József Balogh, Felix Christian Clemen and Bernard Lidický, Max Cuts in Triangle-free Graphs, arXiv:2103.14179 [math.CO], 2021.
Elijah Beregovsky and others, Edges needed to be removed to make graph bipartite, SeqFan mailing list, Oct. 9-13, 2025.
Thomas Bloom, Problem #23, Erdős Problems.
Paul Erdős, Problems and results in graph theory and combinatorial analysis, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen,1975), pages 169-192. Congressus Numerantium, No. XV, 1976.
P. Erdős, E. Győri, and M. Simonovits, How many edges should be deleted to make a triangle-free graph bipartite?, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, 60, 239-263, North-Holland, Amsterdam, 1992.
House of Graphs, Maximal triangle-free graphs.
Leonardo de Lima, Vladimir Nikiforov, and Carla Oliveira, The clique number and the smallest Q-eigenvalue of graphs, Discrete Mathematics, Volume 339, Issue 6, 2016, pages 1744-1752.
FORMULA
a(n) <= n^2/23.5 (Balogh, Clemen, Lidický)
a(n) <= a(n-1) + n/5. (Proof by Martin Fuller: see the SeqFan link.)
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Elijah Beregovsky, Oct 09 2025.
EXTENSIONS
a(23) from Brendan McKay, Oct 16 2025
STATUS
approved