Accession Number:

ADA275652

Title:

A Characterization of Graphs with Interval Two-Step Graphs

Descriptive Note:

Technical rept. Apr-Jul 1993

Corporate Author:

COLORADO UNIV AT DENVER

Report Date:

1993-10-14

Pagination or Media Count:

20.0

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. Interval graphs, Competition graphs, Step graphs.

Subject Categories:

  • Printing and Graphic Arts

Distribution Statement:

APPROVED FOR PUBLIC RELEASE