(Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

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

Résumé

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.
Fichier principal
Vignette du fichier
2012CrespelleGambetteBGW.pdf (175.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00730247 , version 1 (08-09-2012)

Identifiants

  • HAL Id : hal-00730247 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More