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 K1,3 (that is, a star graph with three edges, three leaves, and one 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.
Read more about Claw-free Graph: Examples, Recognition, Enumeration, Matchings, Independent Sets, Coloring, Cliques, and Domination, Structure
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)