Making a trianglefree graph bipartite
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
There are many problems on triangles and trianglefree graphs in the problem paper [1]. The following problem was proposed in 1988.
A problem on making a trianglefree graph bipartite (proposed by Erdös, Faudree, Pach and Spencer [3])
Is it true that every trianglefree graph on \(5n\) vertices can be made bipartite by deleting at most \(n^2\) edges?This conjecture, if true, would be best possible, as can be seen by considering the construction of a \( 5\)partite graph with vertex sets \( S_i\), \( i = 1, \ldots, 5\), on \( n\) vertices each, and putting complete bipartite graphs between \( S_i\) and \( S_{i+1}\) where the index addition is taken modulo \( 5\).
Erdös, Györi and Simonovits [2] proved this conjecture for graphs with at least \( 5n^2\) edges. However, the general conjecture is still open for graphs with \( e\) edges for \( 2n^2 < e \leq 5 n^2\).
Bibliography  

1 
P. Erdös, Some problems on finite and infinite graphs, Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math. 65,
223228, Amer. Math. Soc., Providence, R. I., 1987.

2 
P. Erdös, E. Györi and M. Simonovits, How many edges should be
deleted to make a trianglefree graph bipartite?, Sets, graphs and
numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, 60,
239263, NorthHolland, Amsterdam, 1992.

3 
P. Erdös, R. Faudree, J. Pach and J. H. Spencer, How to make a graph
bipartite, J. Comb. Theory Ser. B 45 (1988), 8698.
