Clique (graph Theory) - Mathematics

Mathematics

Mathematical results concerning cliques include the following.

• Turán's theorem (Turán 1941) gives a lower bound on the size of a clique in dense graphs. If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with vertices and more than edges must contain a three-vertex clique.
• Ramsey's theorem (Graham, Rothschild & Spencer 1990) states that every graph or its complement graph contains a clique with at least a logarithmic number of vertices.
• According to a result of Moon & Moser (1965), a graph with 3n vertices can have at most 3n maximal cliques. The graphs meeting this bound are the Moon–Moser graphs K_3,3,..., a special case of the Turán graphs arising as the extremal cases in Turán's theorem.
• Hadwiger's conjecture, still unproven, relates the size of the largest clique minor in a graph to its chromatic number.
• The Erdős–Faber–Lovász conjecture is another unproven statement relating graph coloring to cliques.

Several important classes of graphs may be defined by their cliques:

• A chordal graph is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the neighbors of each vertex v that come later than v in the ordering form a clique.
• A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
• An interval graph is a graph whose maximal cliques can be ordered in such a way that, for each vertex v, the cliques containing v are consecutive in the ordering.
• A line graph is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
• A perfect graph is a graph in which the clique number equals the chromatic number in every induced subgraph.
• A split graph is a graph in which some clique contains at least one endpoint of every edge.
• A triangle-free graph is a graph that has no cliques other than its vertices and edges.

Additionally, many other mathematical constructions involve cliques in graphs. Among them,

• The clique complex of a graph G is an abstract simplicial complex X(G) with a simplex for every clique in G
• A simplex graph is an undirected graph κ(G) with a vertex for every clique in a graph G and an edge connecting two cliques that differ by a single vertex. It is an example of median graph, and is associated with a median algebra on the cliques of a graph: the median m(A,B,C) of three cliques A, B, and C is the clique whose vertices belong to at least two of the cliques A, B, and C.
• The clique-sum is a method for combining two graphs by merging them along a shared clique.
• Clique-width is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques.
• The intersection number of a graph is the minimum number of cliques needed to cover all the graph's edges.

Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graphs by forbidden complete and complete bipartite subdivisions and minors, respectively.