HOME

TheInfoList



OR:

In the
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
area of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a triangle-free graph is an undirected graph in which no three vertices form a
triangle A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...
of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the ''n''-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.


Triangle finding problem

The triangle finding or triangle detection problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph. It is possible to test whether a graph with m edges is triangle-free in time \tilde O\bigl(m^\bigr) where the \tilde O hides sub-polynomial factors. Here \omega is the exponent of fast matrix multiplication; \omega<2.372 from which it follows that triangle detection can be solved in time O(m^). Another approach is to find the trace of , where is the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
of the graph. The trace is zero if and only if the graph is triangle-free. For dense graphs, it is more efficient to use this simple algorithm which again relies on matrix multiplication, since it gets the time complexity down to O(n^), where n is the number of vertices. Even if matrix multiplication algorithms with time O(n^2) were discovered, the best time bounds that could be hoped for from these approaches are O(m^) or O(n^2). In fine-grained complexity, the ''sparse triangle hypothesis'' is an unproven computational hardness assumption asserting that no time bound of the form O(m^) is possible, for any \delta>0, regardness of what algorithmic techniques are used. It, and the corresponding ''dense triangle hypothesis'' that no time bound of the form O(n^) is possible, imply lower bounds for several other computational problems in combinatorial optimization and computational geometry. As showed, triangle-free graph recognition is equivalent in complexity to median graph recognition; however, the current best algorithms for median graph recognition use triangle detection as a subroutine rather than vice versa. The decision tree complexity or query complexity of the problem, where the queries are to an oracle which stores the adjacency matrix of a graph, is . However, for
quantum algorithm In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
s, the best known lower bound is , but the best known algorithm is .


Independence number and Ramsey theory

An independent set of \lfloor\sqrt\rfloor vertices (where \lfloor\cdot\rfloor is the
floor function In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
) in an ''n''-vertex triangle-free graph is easy to find: either there is a vertex with at least \lfloor\sqrt\rfloor neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than \lfloor\sqrt\rfloor neighbors (in which case any maximal independent set must have at least \lfloor\sqrt\rfloor vertices). This bound can be tightened slightly: in every triangle-free graph there exists an independent set of \Omega(\sqrt) vertices, and in some triangle-free graphs every independent set has O(\sqrt) vertices. One way to generate triangle-free graphs in which all independent sets are small is the ''triangle-free process'' in which one generates a maximal triangle-free graph by repeatedly adding randomly chosen edges that do not complete a triangle. With high probability, this process produces a graph with independence number O(\sqrt). It is also possible to find
regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
s with the same properties. These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,''t'') of the form \Theta(\tfrac): if the edges of a complete graph on \Omega(\tfrac) vertices are colored red and blue, then either the red graph contains a triangle or, if it is triangle-free, then it must have an independent set of size ''t'' corresponding to a clique of the same size in the blue graph.


Coloring triangle-free graphs

Much research about triangle-free graphs has focused on
graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
. Every
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
(that is, every 2-colorable graph) is triangle-free, and Grötzsch's theorem states that every triangle-free
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
may be 3-colored. However, nonplanar triangle-free graphs may require many more than three colors. The first construction of triangle free graphs with arbitrarily high chromatic number is due to Tutte (writing as Blanche Descartes). This construction started from the graph with a single vertex say G_1 and inductively constructed G_ from G_ as follows: let G_ have n vertices, then take a set Y of k(n-1)+1 vertices and for each subset X of Y of size n add a disjoint copy of G_ and join it to X with a matching. From the
pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...
it follows inductively that G_ is not k colourable, since at least one of the sets X must be coloured monochromatically if we are only allowed to use k colours. defined a construction, now called the Mycielskian, for forming a new triangle-free graph from another triangle-free graph. If a graph has chromatic number ''k'', its Mycielskian has chromatic number ''k'' + 1, so this construction may be used to show that arbitrarily large numbers of colors may be needed to color nonplanar triangle-free graphs. In particular the
Grötzsch graph In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...
, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property. and showed that the number of colors needed to color any ''m''-edge triangle-free graph is :O \left(\frac \right) and that there exist triangle-free graphs that have chromatic numbers proportional to this bound. There have also been several results relating coloring to minimum degree in triangle-free graphs. proved that any ''n''-vertex triangle-free graph in which each vertex has more than 2''n''/5 neighbors must be bipartite. This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2''n''/5 neighbors per vertex. Motivated by this result, conjectured that any ''n''-vertex triangle-free graph in which each vertex has at least ''n''/3 neighbors can be colored with only three colors; however, disproved this conjecture by finding a counterexample in which each vertex of the Grötzsch graph is replaced by an independent set of a carefully chosen size. showed that any ''n''-vertex triangle-free graph in which each vertex has more than 10''n''/29 neighbors must be 3-colorable; this is the best possible result of this type, because Häggkvist's graph requires four colors and has exactly 10''n''/29 neighbors per vertex. Finally, proved that any ''n''-vertex triangle-free graph in which each vertex has more than ''n''/3 neighbors must be 4-colorable. Additional results of this type are not possible, as Hajnalsee . found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)''n'' for any ε > 0.


See also

* Andrásfai graph, a family of triangle-free circulant graphs with diameter two * Henson graph, an infinite triangle-free graph that contains all finite triangle-free graphs as induced subgraphs * Shift graph, a family of triangle-free graphs with arbitrarily high chromatic number *The Kneser graph KG_ is triangle free and has chromatic number k + 1 *
Monochromatic triangle In graph theory and theoretical computer science, 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 subgraphs. It is NP-complete but fixe ...
problem, the problem of partitioning the edges of a given graph into two triangle-free graphs * Ruzsa–Szemerédi problem, on graphs in which every edge belongs to exactly one triangle


References


Notes


Sources

* *. *. *. *. *. *. *. * *. *. *. *. *. *. *. *. *. *. *. * *. *. *. *. *. *. *. *.


External links

* {{Citation , url=http://www.graphclasses.org/classes/gc_371.html , title=Graphclass: triangle-free , work =Information System on Graph Classes and their Inclusions Graph families