Series: 2006-59, Preprints
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