Sources and sinks in comparability graphs (Q1368667): Difference between revisions

Let \(G^v\) be the graph obtained from \(G\) by adding a new vertex \(v'\) adjacent only to the fixed vertex \(v\). The authors prove the following theorem: Let \(G\) be a comparability graph and \(S\subset V(G)\). Then \(S\) is a source set iff \(G^v\) is a comparability graph and no odd induced path joins \(v\) to \(w\), for all \(v,w\in S\). This theorem can be used to formulate an algorithm for finding transitive orientations with prescribed sources in a graph.