Zurück zu den Preprints des Jahres 2006


2006-59

On transitive orientations of G - e

by Andresen, Michael.


Series: 2006-59, Preprints

MSC:

Abstract:
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.

Keywords:
comparability graph; transitive orientation; edge deletion; implication classes