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 such graphs 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.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.