Graph Family Characterizations
Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximal-clique irreducible and hereditary maximal-clique irreducible graphs. A graph is said to be maximal-clique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximal-clique irreducible if the same property is true for every induced subgraph. Hereditary maximal-clique irreducible graphs include triangle-free graphs, bipartite graphs, and interval graphs.
Cographs can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.
Read more about this topic: Maximal Independent Set
Famous quotes containing the words graph and/or family:
“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)
“... the school should be an appendage of the family state, and modeled on its primary principle, which is, to train the ignorant and weak by self-sacrificing labor and love; and to bestow the most on the weakest, the most undeveloped, and the most sinful.”
—Catherine E. Beecher (1800–1878)