06-59
On transitive orientations of G - e
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.