Premium
A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular‐arc graphs, and nested interval graphs
Author(s) -
Skrien Dale J.
Publication year - 1982
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190060307
Subject(s) - combinatorics , mathematics , indifference graph , interval graph , pathwidth , chordal graph , split graph , block graph , cograph , discrete mathematics , comparability graph , trapezoid graph , maximal independent set , 1 planar graph , pancyclic graph , graph , line graph
Given a set F of digraphs, we say a graph G is a F ‐ graph (resp., F *‐ graph ) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F . It is proved that all the classes of graphs mentioned in the title are F ‐graphs or F *‐graphs for subsets F of a set of three digraphs.