Questions tagged [forbidden-subgraphs]

For questions related to graphs which do not contain any element of a family of graphs as a subgraph. E.g., Kuratowski characterized planar graphs as those which do not have either a subdivision of the complete graph K_5 on five vertices or a subdivision of the complete bipartite graph K_{3,3} as a subgraph.

A graph $G$ is a forbidden-subgraph with respect to a give property if $G$ does not have the property, and any graph that contains $G$ as a subgraph does not have the property.

Examples

  • The quintessential example of this is Kuratowski's characterization of planar graphs as those which do not have either a subdivision of the complete graph $K_5$ on five vertices or a subdivision of the complete bipartite graph $K_{3,3}$ as a subgraph.

  • A lattice—a type of directed graph—is distributive if it does not contain one two forbidden sublattices. See Wikipedia for details.

21 questions