A387954 The number of triangle-free graphs on n vertices which require the most edges to be removed to make them bipartite.

1, 2, 3, 7, 1, 3, 19, 7, 86, 1, 14, 2, 8, 1, 1, 34, 44, 7, 5, 1, 85, 1076, 6

Offset

1,2

Comments

The extremal graphs for n=23 are 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, Oct 16 2025

Links

Table of n, a(n) for n=1..23.

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.

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.

B. D. McKay, Extremal graphs for bipartization of triangle-free graphs.

SeqFan, Edges needed to be removed to make graph bipartite, 2025.

Crossrefs

Cf. A389646 (number of edges that need to be removed).

Cf. A216783, A280020.

Sequence in context: A023048 A083521 A104691 * A011160 A068960 A358969

Adjacent sequences: A387951 A387952 A387953 * A387955 A387956 A387957

Keyword

nonn,more

Author

Elijah Beregovsky, Oct 12 2025

Extensions

a(23) from Brendan McKay, Oct 16 2025

Status

approved