Zurück zu den Preprints des Jahres 2006


On transitive orientations of G - e

by Andresen, Michael.

Series: 2006-59, Preprints


A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge e from E we explore the question whether the graph G - e, obtained by removing the undirected edge e, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterisation of all those edges.

comparability graph; transitive orientation; edge deletion; implication classes