Erdős Problem #23 — Making triangle-free graphs on vertices bipartite
Is it true that every graph of vertices which contains no triangle can be made two-chromatic by the omission of at most edges? It is easy to see that if this is true it is best possible.
References
Additional 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.
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.