Skip to Main content Skip to Navigation
Conference papers

(Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs

Abstract : 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 Omega(log n). We also provide an Omega(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 min-max 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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download
Contributor : Philippe Gambette Connect in order to contact the contributor
Submitted on : Saturday, September 8, 2012 - 10:51:23 AM
Last modification on : Thursday, January 20, 2022 - 5:29:51 PM
Long-term archiving on: : Sunday, December 9, 2012 - 3:05:08 AM


Files produced by the author(s)


  • HAL Id : hal-00730247, version 1


Christophe Crespelle, Philippe Gambette. (Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs. Bordeaux Graph Workshop, Nov 2012, France. pp.2. ⟨hal-00730247⟩



Les métriques sont temporairement indisponibles