FORBIDDEN MINORS Meaning and
Definition
-
Forbidden minors refer to specific substructures that cannot appear in a given class of graphs. In the context of graph theory, a minor of a graph refers to a smaller graph obtained by deleting edges, deleting isolated vertices, and contracting edges. The concept of forbidden minors allows researchers to identify a set of forbidden subgraphs, which, if present in a given graph, imply that the graph does not belong to a certain class or family.
The forbidden minors concept holds significant importance in graph theory, as it helps classify different graph families and provides insights into the structure and properties of graphs. By identifying forbidden minors, researchers can establish necessary and sufficient conditions for a graph to be a member of a specific graph class.
The definition of forbidden minors can vary depending on the category of graphs being studied. For example, in the study of planar graphs, certain subgraphs such as the complete graph on five vertices (K5) or the complete bipartite graph on three vertices (K3,3) are considered forbidden minors as they characterize a non-planar graph. Similarly, in the study of minor-closed graph families, forbidden minors may involve specific subgraphs that are not isomorphic to certain known graph families, such as the wheel or the theta graph.
Overall, forbidden minors are powerful tools in graph theory to define and distinguish different graph classes, allowing researchers to explore the properties and characteristics of graphs in a structured and rigorous manner.
Etymology of FORBIDDEN MINORS
The term "forbidden minors" originates from the field of graph theory, specifically in the study of minors. The word "forbidden" implies that certain objects or elements are not allowed or prohibited. In the context of graph theory, a minor of a graph G is a graph that can be obtained by replacing edges (and possibly vertices) of G. Forbidden minors refer to specific graphs that are not allowed to be obtained as minors of a given graph. This concept is often used to understand the structure and properties of graphs.
