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:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“The man who promised to reinforce American families is now eager to pull the plug on Big Bird and Barney.”
—Leslie Harris, U.S. political activist. As quoted in Newsweek magazine, p. 23 (December 19, 1994)