Forbidden graph characterization
Encyclopedia
A forbidden graph characterization is a method of specifying
Characterization (mathematics)
In mathematics, the statement that "Property P characterizes object X" means, not simply that X has property P, but that X is the only thing that has property P. It is also common to find statements such as "Property Q characterises Y up to isomorphism". The first type of statement says in...

 a family of graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

, or hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...

, structures.
Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

 a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction
Edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it previously connected. Edge contraction is a fundamental operation in the theory of graph minors...

 or subdivision) that which is forbidden. Thus, the forbidden structure might be one of:
  • subgraphs,
  • graph minors,
  • homeomorphic
    Homeomorphism (graph theory)
    In graph theory, two graphs G and G' are homeomorphic if there is an isomorphism from some subdivision of G to some subdivision of G'...

     subgraphs (also called topological minors).

(Such forbidden structures can also be called obstruction sets.)

Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function).

A well-known characterization of this kind is the Kuratowski theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

. Another is the Robertson–Seymour theorem
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...

 that proves the existence of a forbidden minor characterization for several graph families.

List of forbidden characterizations for graphs and hypergraphs

Family Forbidden graphs Relation Reference
Forests loops, pairs of parallel edges, and cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...

 of all lengths
subgraph Definition
a loop (for multigraphs) or a triangle K3 (for simple graphs) graph minor Definition
Claw-free graphs star
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...

 K1,3
induced subgraph Definition
Comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...

s
induced subgraph
Triangle-free graph
Triangle-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 girth ≥ 4, graphs with no induced 3-cycle, or locally...

s
triangle K3 induced subgraph Definition
Planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s
K5 and K3,3 homeomorphic subgraph Kuratowski theorem
K5 and K3,3 graph minor Wagner's theorem
Outerplanar graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...

s
K4 and K2,3 graph minor , p. 107
Graphs of fixed genus a finite obstruction set graph minor , p. 275
Apex graph
Apex graph
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. We say an apex, not the apex because an apex graph may have more than one apex...

s
a finite obstruction set graph minor
Linklessly embeddable graphs
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the...

The Petersen family
Petersen family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph....

graph minor
Bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

s
odd cycles subgraph
Chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

s
cycles of length 4 or more induced subgraph
Perfect graph
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s
cycles of odd length 5 or more or their complements
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

induced subgraph
Line graph of graph
Line graph
In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

s
nine forbidden subgraphs (listed here) induced subgraph
Graph unions of cactus graph
Cactus graph
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block is an edge or a cycle.-Properties:Cacti are outerplanar graphs...

s
the four-vertex diamond graph
Diamond graph
In 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....

formed by removing an edge from the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

 K4
graph minor
Ladder graph
Ladder graph
In the mathematical field of graph theory, the ladder graph Ln is a planar undirected graph with 2n vertices and n+2 edges....

s
K2,3 and its dual graph
Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...

homeomorphic subgraph
Helly circular-arc graphs induced subgraph
split graph
Split graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set...

s
induced subgraph
treewidth ≤ 2 (branchwidth ≤ 2) K4 graph minor , p. 327
treewidth ≤ 3 K5, octahedron
Octahedron
In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....

, pentagonal prism
Pentagonal prism
In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with 7 faces, 15 edges, and 10 vertices.- As a semiregular polyhedron :...

, Wagner graph
Wagner graph
In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.-Properties:...

graph minor
branchwidth ≤ 3 K5, octahedron
Octahedron
In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....

, cube
Cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...

, Wagner graph
Wagner graph
In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.-Properties:...

graph minor
Complement-reducible graphs (cographs)
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...

4-vertex path P4 induced subgraph
Trivially perfect graphs 4-vertex path P4 and 4-vertex cycle C4 induced subgraph
Threshold graph
Threshold graph
In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:#Addition of a single isolated vertex to the graph....

s
4-vertex path P4, 4-vertex cycle C4, and complement of C4 induced subgraph
Line graph of 3-uniform linear hypergraphs a finite list of forbidden induced subgraphs with minimum degree at least 19 induced subgraph
Line graph of k-uniform linear hypergraphs, k > 3 a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 induced subgraph
General theorems
a family defined by an induced-hereditary property a (not necessarily finite) obstruction set induced subgraph
a family defined by an minor-hereditary property a finite obstruction set graph minor Robertson–Seymour theorem
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK