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:
“A parent who from his own childhood experience is convinced of the value of fairy tales will have no difficulty in answering his child’s questions; but an adult who thinks these tales are only a bunch of lies had better not try telling them; he won’t be able to related them in a way which would enrich the child’s life.”
—Bruno Bettelheim (20th century)
“Notwithstanding the unaccountable apathy with which of late years the Indians have been sometimes abandoned to their enemies, it is not to be doubted that it is the good pleasure and the understanding of all humane persons in the Republic, of the men and the matrons sitting in the thriving independent families all over the land, that they shall be duly cared for; that they shall taste justice and love from all to whom we have delegated the office of dealing with them.”
—Ralph Waldo Emerson (1803–1882)