Comparability graph
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
The undirected graph $(P,E)$ on a partially ordered set $(P,{\le})$ in which two points are adjacent if they are comparable; that is, $xy$ is an edge of the graph if and only if $x < y$ or $y < x$. Comparability graphs are characterised by the property that in any odd length closed path $x_1,\ldots,x_{2n+1}$ with $n \ge 2$ (so all $x_i,x_{i+1}$ are adjacent) there exists at least one "chord" $x_i,x_{i+2}$ (subscripts being taken in cyclic order).
References
- Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications 3. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 Zbl 0919.05001
How to Cite This Entry:
Comparability graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Comparability_graph&oldid=54456
Comparability graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Comparability_graph&oldid=54456