Families of Graphs That Are Perfect
Some of the more well-known perfect graphs are:
- Bipartite graphs, the graphs that can be colored with two colors, including the forests, graphs with no cycles.
- The line graphs of bipartite graphs (see König's theorem). The rook's graphs (line graphs of complete bipartite graphs) are a special case.
- Chordal graphs, the graphs in which every cycle of four or more vertices has a chord, an edge between two vertices that are not consecutive in the cycle. These include the forests, k-trees (maximal graphs with a given treewidth), split graphs (graphs that can be partitioned into a clique and an independent set), block graphs (graphs in which every biconnected component is a clique), interval graphs (graphs in which each vertex represents an interval of a line and each edge represents a nonempty intersection between two intervals), trivially perfect graphs (interval graphs for nested intervals), threshold graphs (graphs in which two vertices are adjacent when their total weight exceeds a numerical threshold), windmill graphs (formed by joining equal cliques at a common vertex), and strongly chordal graphs (chordal graphs in which every even cycle of length six or more has an odd chord).
- Comparability graphs formed from partially ordered sets by connecting pairs of elements by an edge whenever they are related in the partial order. These include the bipartite graphs, the complements of interval graphs, the trivially perfect graphs, the threshold graphs, the windmill graphs, the permutation graphs (graphs in which the edges represent pairs of elements that are reversed by a permutation), and the cographs (graphs formed by recursive operations of disjoint union and complementation).
- Perfectly orderable graphs, the graphs that can be ordered in such a way that a greedy coloring algorithm is optimal on every induced subgraph. These include the bipartite graphs, the chordal graphs, the comparability graphs, the distance-hereditary graphs (in which shortest path distances in connected induced subgraphs equal those in the whole graph), and the wheel graphs that have an odd number of vertices.
- Trapezoid graphs, the intersection graphs of trapezoids whose parallel pairs of edges lie on two parallel lines. These include the interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, and permutation graphs; their complements are a subset of the comparability graphs.
Read more about this topic: Perfect Graph
Famous quotes containing the words families of, families and/or perfect:
“Families have always been in flux and often in crisis; they have never lived up to nostalgic notions about “the way things used to be.” But that doesn’t mean the malaise and anxiety people feel about modern families are delusions, that everything would be fine if we would only realize that the past was not all it’s cracked up to be. . . . Even if things were not always right in families of the past, it seems clear that some things have newly gone wrong.”
—Stephanie Coontz (20th century)
“Many older wealthy families have learned to instill a sense of public service in their offspring. But newly affluent middle-class parents have not acquired this skill. We are using our children as symbols of leisure-class standing without building in safeguards against an overweening sense of entitlement—a sense of entitlement that may incline some young people more toward the good life than toward the hard work that, for most of us, makes the good life possible.”
—David Elkind (20th century)
“The complete life, the perfect pattern, includes old age as well as youth and maturity. The beauty of the morning and the radiance of noon are good, but it would be a very silly person who drew the curtains and turned on the light in order to shut out the tranquillity of the evening. Old age has its pleasures, which, though different, are not less than the pleasures of youth.”
—W. Somerset Maugham (1874–1965)