Metraipolis › archive › dc_045dff6a5781
Forbidden graph characterization — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Forbidden_graph_characterization
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T11:32:54.320Z
- SHA-256 of the archived text
92971ebc269d2dfa9695b3596256ced4975dbc58bec33031f81b200e1955242c- Stable URL of this page
https://metraipolis.com/documento/dc_045dff6a5781
How to cite
Forbidden graph characterization — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Forbidden_graph_characterization (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_045dff6a5781 (Metraipolis archive dc_045dff6a5781, sha256 92971ebc269d2dfa9695b3596256ced4975dbc58bec33031f81b200e1955242c)
BibTeX
@misc{dc045dff6a5781,
title = {Forbidden graph characterization — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Forbidden_graph_characterization},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_045dff6a5781; sha256 92971ebc269d2dfa9695b3596256ced4975dbc58bec33031f81b200e1955242c},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Forbidden_graph_characterization. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 K5 and the complete bipartite graph K3,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). Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»). Fonte: Wikipedia in inglese, voce «Forbidden graph characterization» — https://en.wikipedia.org/wiki/Forbidden_graph_characterization Wikidata Q5467387: «describing a family of graphs by excluding certain (sub)graphs» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5467387 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Forbidden_graph_characterization?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1352725274, consultata il 2026-10-06T09:55:39.874Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0162668f6a8333caa2a1f215bd4456d687aaa3a7ba305d0a55ad3f2d566f5ff0