Monochromatic triangle

From Wikipedia, the free encyclopedia

The monochromatic triangle problem is a decision problem that is known to be NP-complete.

Input: An n-node undirected graph G(V,E) with node set V and edge set E.

Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and E2, such that neither of the two graphs G1(V,E1) and G2(V,E2) contain a triangle? That is to say: for all nodes in E1 or E2 there does not exist a set {u,v,w} such that {u,v}, {u,w}, {v,w} are all edges.

[edit] See also

• Ramsey's theorem

[edit] References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT6, pg.191.θ