(Nearly-)tight bounds on the contiguity and linearity of cographs
In this paper we show that the contiguity and linearity of cographs on n  vertices are both O ( log n ) . Moreover, we show that this bound is tight for contiguity as there exists a family of cographs on n  vertices whose contiguity is ? ( log n ) . We also provide an ? ( log n / log log n ) lower bound on the maximum linearity of cographs on n vertices. As a by-product of our proofs, we obtain a minmax theorem, which is worth of interest in itself, stating equality between the rank of a tree and the minimum height of one of its path partitions.
contiguity linearity cographs graph encoding