Monochromatic triangle on:
[Wikipedia]
[Google]
[Amazon]
In
In graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, the monochromatic triangle problem is an algorithmic problem on graphs,
in which the goal is to partition the edges of a given graph into two triangle-free
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
subgraphs. It is NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
but fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
on graphs of bounded treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
.
Problem statement
The monochromatic triangle problem takes as input an n-node undirected graph G(V,E) with node set V and edge set E. The output is a Boolean value, true if the edge set E of G can be partitioned into two disjoint sets E1 and E2, such that both of the two subgraphs G1(V,E1) and G2(V,E2) aretriangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
s, and false otherwise. This decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
is NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
Generalization to multiple colors
The problem may be generalized to triangle-free edge coloring, finding an assignment of colors to the edges of a graph so that no triangle has all three edges given the same color. The monochromatic triangle problem is the special case of triangle-free edge-coloring when there are exactly two colors available. If there exists a two-color triangle-free edge coloring, then the edges of each color form the two sets E1 and E2 of the monochromatic triangle problem. Conversely, if the monochromatic triangle problem has a solution, we can use one color for E1 and a second color for E2 to obtain a triangle-free edge coloring.Connection to Ramsey's theorem
ByRamsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
, for any finite number ''k'' of colors, there exists a number ''n'' such that complete graphs of ''n'' or more vertices do not have triangle-free edge colorings with ''k'' colors. For ''k'' = 2, the corresponding value of ''n'' is 6. That is, the answer to the monochromatic triangle problem on the complete graph ''K''6 is no.
Parameterized complexity
It is straightforward to express the monochromatic triangle problem in the monadic second-orderlogic of graphs
In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that ...
(MSO2), by a logical formula that asserts the existence of a partition of the edges into two subsets such that there do not exist three mutually adjacent vertices whose edges all belong to the same side of the partition. It follows from Courcelle's theorem In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bru ...
that the monochromatic triangle problem is fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
on graphs of bounded treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
. More precisely, there is an algorithm for solving the problem whose running time is the number of vertices of the input graph multiplied by a quickly-growing but computable function of the treewidth..
References
{{reflist NP-complete problems Graph coloring