Use of MAX-CUT for Ramsey Arrowing of Triangles

Alexander Lange, Stanisław Radziszowski, Xiaodong Xu

In 1967, Erdős and Hajnal asked the question: Does there exist a $K_4$-free graph that is not the union of two triangle-free graphs? Finding such a graph involves solving a special…