Related Families of Graphs
Interval graphs are chordal graphs and hence perfect graphs. Their complements belong to the class of comparability graphs, and the comparability relations are precisely the interval orders.
The interval graphs that have an interval representation in which every two intervals are either disjoint or nested are the trivially perfect graphs.
Proper interval graphs are interval graphs that have an interval representation in which no interval properly contains any other interval; unit interval graphs are the interval graphs that have an interval representation in which each interval has unit length. Every proper interval graph is a claw-free graph. However, the converse is not true. Every claw-free graph is not necessarily a proper interval graph. If the collection of segments in question is a set, i.e., no repetitions of segments is allowed, then the graph is unit interval graph if and only if it is proper interval graph.
The intersection graphs of arcs of a circle form circular-arc graphs, a class of graphs that contains the interval graphs. The trapezoid graphs, intersections of trapezoids whose parallel sides all lie on the same two parallel lines, are also a generalization of the interval graphs.
The pathwidth of an interval graph is one less than the size of its maximum clique (or equivalently, one less than its chromatic number), and the pathwidth of any graph G is the same as the smallest pathwidth of an interval graph that contains G as a subgraph.
The connected triangle-free interval graphs are exactly the caterpillar trees.
Read more about this topic: Interval Graph
Famous quotes containing the words related and/or families:
“Perhaps it is nothingness which is real and our dream which is non-existent, but then we feel think that these musical phrases, and the notions related to the dream, are nothing too. We will die, but our hostages are the divine captives who will follow our chance. And death with them is somewhat less bitter, less inglorious, perhaps less probable.”
—Marcel Proust (1871–1922)
“We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.”
—Urie Bronfenbrenner (b. 1917)