zbMATH — the first resource for mathematics

On transitive orientations of \(G-\widehat e\). (English) Zbl 1193.05140
Summary: A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph \(G=(V,E)\) and an arbitrary edge \(\widehat e\in E\) we explore the question whether the graph \(G-\widehat e\), obtained by removing the undirected edge \(\widehat e\), is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.
05C75 Structural characterization of families of graphs
05C20 Directed graphs (digraphs), tournaments
90B35 Deterministic scheduling theory in operations research
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI