Forbidden graph characterizationIn graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.
Graph automorphismIn the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph G = (V, E) is a permutation σ of the vertex set V, such that the pair of vertices (u, v) form an edge if and only if the pair (σ(u), σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs.
Acyclic coloringIn graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of a graph G is the fewest colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. A(G) ≤ 2 if and only if G is acyclic. Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following: A(G) ≤ 4 if Δ(G) = 3. A(G) ≤ 5 if Δ(G) = 4. A(G) ≤ 7 if Δ(G) = 5. A(G) ≤ 12 if Δ(G) = 6.
Diamond graphIn the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromatic number 3 and chromatic index 3. It is also a 2-vertex-connected and a 2-edge-connected, graceful, Hamiltonian graph. A graph is diamond-free if it has no diamond as an induced subgraph. The triangle-free graphs are diamond-free graphs, since every diamond contains a triangle.
Perfect graph theoremIn graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.
Ramsey's theoremIn 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, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.
