Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Forbidden graph characterization
Summary
In 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. For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing (in which case it belongs to the family of planar graphs) or it has a subdivision of at least one of these two graphs as a subgraph (in which case it does not belong to the planar graphs).
More generally, a forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures, by specifying substructures that are forbidden to exist within any graph in the family. Different families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might be one of:
subgraphs, smaller graphs obtained from subsets of the vertices and edges of a larger graph,
induced subgraphs, smaller graphs obtained by selecting a subset of the vertices and using all edges with both endpoints in that subset,
homeomorphic subgraphs (also called topological minors), smaller graphs obtained from subgraphs by collapsing paths of degree-two vertices to single edges, or
graph minors, smaller graphs obtained from subgraphs by arbitrary edge contractions.
The set of structures that are forbidden from belonging to a given graph family can also be called an obstruction set for that family.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.