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

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