In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible.
Max-Cut is APX-complete on bounded-degree graphs [PY91], and in fact APX-complete on cubic graphs (i.e. graphs of degree 3) [AK00].
Max-Cut is NP-complete on triangle-free graphs of degree at most 3 [LY80] (triangle-free means that the input graph does not contain K_3, the complete graph on 3 vertices, as a subgraph).
Question: Is Max-Cut APX-complete on triangle-free graphs? (Note: arbitrary degrees allowed)
Thank you.
UPDATE: An answer has been found, but I would still be interested in a reference for this result, if there is any.
References:
[AK00] P. Alimonti and V. Kann: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1-2): 123-134, 2000. doi: 10.1016/S0304-3975(98)00158-3
[LY80] J.M. Lewis and M. Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230, 1980. doi: 10.1016/0022-0000(80)90060-4
[PY91] C.H Papadimitriou and M. Yannakakis: Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43(3): 425-440, 1991. doi: 10.1016/0022-0000(91)90023-X