Namespaces
Variants
Actions

Difference between revisions of "Cograph"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Cograph)
 
m (link)
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.

Revision as of 19:26, 17 January 2016

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