Monochromatic Triangle

Input

Graph $G = (V, E)$.

Question

Is there a partition of $E$ into two disjoint sets $E_1$, $E_2$ such that neither $G_1 = (V, E_1)$ nor $G_2 = (V, E_2)$ contains a triangle?

Classes

• NP-complete

Comments

Variants in which triangle is replaced by any larger fixed complete graph are also NP-complete. Variants in which triangle is replaced by k-star (a single degree $k$ vertex adjacent to $k$ degree one vertices) is solvable in polynomial time (Burr et al., 1976).

Proofs

NP-complete

Transformation from 3-Satisfiability.

Reducible from

• 3-Satisfiability

References

• Burr, S. A., Erdős, P., & Lovasz, L. (1976). On graphs of Ramsey type. ARS COMBINATORIA, 1.