Monochromatic triangle

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.

See also

• Ramsey's theorem

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.θ

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: NP-complete problems Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем сделать НИР Blue Rock Records Mineirão Look at other dictionaries: Ramsey's theorem — This article goes into technical details quite quickly. For a slightly gentler introduction see Ramsey theory. In combinatorics, Ramsey s theorem states that in any colouring of the edges of a sufficiently large complete graph (that is, a simple… …   Wikipedia Sim (pencil game) — The game of Sim is played by two players, Red and Blue, on a board consisting of six dots ( vertices ). Each dot is connected to each other with a line.Two players take turns coloring any uncolored lines. One player colors in red, and the other… …   Wikipedia Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia Almost surely — In probability theory, one says that an event happens almost surely (a.s.) if it happens with probability one. The concept is analogous to the concept of almost everywhere in measure theory. It is often encountered in questions that involve… …   Wikipedia List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia CIE 1931 color space — In the study of color perception, one of the first mathematically defined color spaces is the CIE 1931 XYZ color space, created by the International Commission on Illumination (CIE) in 1931.[1][2] The CIE XYZ color space was derived from a series …   Wikipedia Gamut — This article is about color gamut. For other uses, see Gamut (disambiguation). A typical CRT gamut. The grayed out horseshoe shape is the entire range of possible chromaticities, displayed in the CIE 1931 chromaticity diagram format (see below).… …   Wikipedia Monochromator — in a x ray beamline at the Advanced Photon Source, Argonne National Laboratory. A monochromator is an optical device that transmits a mechanically selectable narrow band of wavelengths of light or other radiation chosen from a wider range of… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”