Metraipolis › archive › dc_d317cd86963d
Claw-free graph — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Claw-free_graph
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T19:33:58.649Z
- SHA-256 of the archived text
4552801992f3e6ade1ae30dc1b431b5524b87a140135353047e913dad823af5b- Stable URL of this page
https://metraipolis.com/documento/dc_d317cd86963d
How to cite
Claw-free graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Claw-free_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d317cd86963d (Metraipolis archive dc_d317cd86963d, sha256 4552801992f3e6ade1ae30dc1b431b5524b87a140135353047e913dad823af5b)
BibTeX
@misc{dcd317cd86963d,
title = {Claw-free graph — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Claw-free_graph},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d317cd86963d; sha256 4552801992f3e6ade1ae30dc1b431b5524b87a140135353047e913dad823af5b},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Claw-free_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K 1 , 3 {\displaystyle K_{1,3}} (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph. Claw-free graphs were initially studied as a generalization of line graphs, and gained additional motivation through three key discoveries about them: the fact that all claw-free connected graphs of even order have perfect matchings, the discovery of polynomial time algorithms for finding maximum independent sets in claw-free graphs, and the characterization of claw-free perfect graphs. They are the subject of hundreds of mathematical research papers and several surveys.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Claw-free graph» — https://en.wikipedia.org/wiki/Claw-free_graph
Wikidata Q5129750 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5129750
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Claw-free_graph?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 1360630479, consultata il 2026-10-15T18:43:45.972Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 38c74c5e6fc9e0842efbb45c4faeb08cc28a2646a3f524fb0bba6923e6879f95