ScholarLens Back to search
1995•Journal of Graph TheoryRequires access

Pseudo‐Interval Graphs

Erik O. Brauner, Richard A. Brauldi, Elizabeth S. N. Sneyd

Open publisher page 1 citations

Abstract

Abstract We study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The complements of pseudo‐interval graphs are comparability graphs but unlike interval graphs, pseudo‐interval graphs are only weakly triangulated. We characterize trees and complements of trees which are pseudo‐interval graphs. Finally we determine all minimal non‐pseudointerval graphs on eight or fewer vertices whose complements are comparability graphs and which are weakly triangulated. © 1995 John Wiley & Sons; Inc.

About this research paper

What this paper is about

Abstract We study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The complements of pseudo‐interval graphs are comparability graphs but unlike interval graphs, pseudo‐interval graphs are only weakly triangulated. We characterize trees and complements of trees which are pseudo‐interval graphs. Finally we determine all minimal non‐pseudointerval graphs on eight or fewer vertices whose complements are comparability graphs and which are weakly triangulated. © 1995 John Wiley & Sons; Inc.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Abstract We study a class of perfect graphs which, because they generalize interval graphs, we call pseudo‐interval graphs. Like interval graphs, their vertices correspond to intervals of a linearly ordered set, but a modified definition of intersection is used in order to determine edges. The complements of pseudo‐interval graphs are comparability graphs but unlike interval graphs, pseudo‐interval graphs are only weakly triangulated. We characterize trees and complements of trees which are pseudo‐interval graphs. Finally we determine all minimal non‐pseudointerval graphs on eight or fewer vertices whose complements are comparability graphs and which are weakly triangulated. © 1995 John Wiley & Sons; Inc.

Key concepts: Interval graph, Indifference graph, Combinatorics, Mathematics, Chordal graph, Interval (graph theory), Trapezoid graph, Pathwidth

Related papers

Related paper 1Related paper 2
Back to paper searchBrowse research topicsOriginal source
Pseudo‐Interval Graphs — Research Paper | ScholarLens