(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 metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00730247
Contributor : Philippe Gambette <>
Submitted on : Saturday, September 8, 2012 - 10:51:23 AM
Last modification on : Wednesday, November 20, 2019 - 3:17:41 AM
Long-term archiving on: Sunday, December 9, 2012 - 3:05:08 AM

File

2012CrespelleGambetteBGW.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00730247, version 1

Citation

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

Share

Metrics

Record views

488

Files downloads

145