Difference between revisions of "Cograph"
From Encyclopedia of Mathematics
(Start article: Cograph) |
m (→References: isbn link) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
''component reducible graph'' | ''component reducible graph'' | ||
| − | An unoriented [[graph]] obtained from the single-vertex graph by the operations of disjoint union and complementation. They are characterised by having no induced subgraph $P_4$, the path of length $4$. | + | An unoriented [[graph]] obtained from the single-vertex graph by the operations of disjoint union and complementation. They are characterised by having no [[induced subgraph]] $P_4$, the path of length $4$. |
They are the [[comparability graph]]s of [[series-parallel order]]s. | They are the [[comparability graph]]s of [[series-parallel order]]s. | ||
==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}} |
* Rival, Ivan (ed.) ''Graphs and order. The role of graphs in the theory of ordered sets and its applications'' Reidel (1985) {{ZBL|0549.00002}} | * Rival, Ivan (ed.) ''Graphs and order. The role of graphs in the theory of ordered sets and its applications'' Reidel (1985) {{ZBL|0549.00002}} | ||
Latest revision as of 07:27, 14 November 2023
component reducible graph
An unoriented graph obtained from the single-vertex graph by the operations of disjoint union and complementation. They are characterised by having no induced subgraph $P_4$, the path of length $4$.
They are the comparability graphs of series-parallel orders.
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
- Rival, Ivan (ed.) Graphs and order. The role of graphs in the theory of ordered sets and its applications Reidel (1985) Zbl 0549.00002
How to Cite This Entry:
Cograph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cograph&oldid=37464
Cograph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cograph&oldid=37464