Sources and sinks in comparability graphs
type: Item
instance of: scholarly article
title: Sources and sinks in comparability graphs
zbMATH Open document ID: 0890.05067
DOI: 10.1023/A:1005803107931
published in: Order
publication date: 1997-09-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1067855
zbMATH Keywords: comparability graph
zbMATH Keywords: source set
zbMATH Keywords: algorithm
zbMATH Keywords: transitive orientations
zbMATH Keywords: sources
author: Celina M. H. de Figueiredo
author: John Gimbel
author: Célia P. de Mello
author: Jayme L. Szwarcfiter
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: a:1005803107931
OpenAlex ID: W200931882
description: scientific article; zbMATH DE number 1067855