Difference between revisions of "Comparability graph"
From Encyclopedia of Mathematics
(Start article: Comparability graph) |
m (→References: isbn link) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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 | + | 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==== | ====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}} | + | * 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}} |
{{TEX|done}} | {{TEX|done}} | ||
Latest revision as of 18:48, 14 November 2023
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=37406
Comparability graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Comparability_graph&oldid=37406