← All problems

Erdős Problem #23 — Making triangle-free graphs on 5n5n vertices bipartite

55 years old · traced to

Is it true that every graph of 5n5n vertices which contains no triangle can be made two-chromatic by the omission of at most n2n^2 edges? It is easy to see that if this is true it is best possible.

References

P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf. Oxford, 1969), Academic Press (1971), 97-109.

Source: P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf. Oxford, 1969), Academic Press (1971), 97-109.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.