Skip to Main content Skip to Navigation
Conference papers

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

Christophe Crespelle 1, 2 Philippe Gambette 3 
1 DNET - Dynamic Networks
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 : Friday, February 4, 2022 - 3:20:06 AM
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⟩



Record views


Files downloads