View source for Threshold graph

{{MSC|05C}}

A graph with [[Dilworth number]] $1$: for any two vertices $x,y$, one of the neighbourhoods $N(x)$, $N(y)$ contains the other.   Such graphs are characterised by having no induced subgraph of the form $K_{2,2}$ (complete bipartite on $2+2$ points) , $C_4$ (cycle of length $4$) or $P_4$ (path of length $4$).  They are the [[comparability graph]]s of [[threshold order]]s.

There is a polynomial time algorithm for computing the Dilworth number of a finite graph.

==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}}

{{TEX|done}}