Carleton University
Technical Report TR-41
February 1984
Intersection Graphs, {B1}-Orientable Graphs and Proper Circular Arc Graphs
Jorge Urrutia
Abstract
A graph G is called a (B1)-orientable graph if there exists an orientationG of G such that if x->y and z->y in G then [x,z] is an edge of G. In this paper we obtain a characterization of {B1}-orien-table graphs. A recognition algorithm for {B1}-orientable graphs is also presented. A simple recognition algorithm for proper circular arc.