Elsevier

Discrete Mathematics

Volume 55, Issue 2, July 1985, Pages 135-149
Discrete Mathematics

Interval graphs and interval orders

https://doi.org/10.1016/0012-365X(85)90042-1Get rights and content
Under an Elsevier user license
open archive

Abstract

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially unique agreeing interval orders are noted, and relationships between interval graphs and interval orders that concern the number of lengths required for interval representations and bounds on lengths of representing intervals are discussed.

Two invariants of the family of interval orders that agree with an interval graph are established, namely magnitude, which affects end-point placements, and the property of having the lengths of all representing intervals between specified bounds. Extremization problems for interval graphs and interval orders are also considered.

Cited by (0)