Naval Postgraduate School
A characterization of graphs with interval two-step graphs
characterization00lund.pdf (1.128Mb)Abstract
One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first consider forbidden subgraph characterizations of graphs with interval two-step graphs. We then characterize a large class of graphs with interval two-step graphs, using the Fulkerson-Gross characterization of interval graphs.
Description
Approved for public release; distribution is unlimited.
NPS Report Number
NPS-MA-93-021Related items
Showing items related by title, author, creator and subject.
-
A Characterization of Graphs With Interval Two-Step Graphs
(Norrth-Holland, 1995);One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless ... -
Chromatic numbers of competition graphs
(Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-020Previous work on competition graphs has emphasized characterization, not only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of characterization ... -
Chromatic numbers of competition graphs
(North-Holland, 1995);Previous work on competition graphs has emphasized characterization, not only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of characterization ...
