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
[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.θ
.svg){kind=small}
