06-59

On transitive orientations of G - e

by Andresen, Michael

 

Preprint series: 06-59, Preprints

ZDM:
K30

 

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


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster