(Nearly-)tight bounds on the contiguity and linearity of cographs - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2014

(Nearly-)tight bounds on the contiguity and linearity of cographs

Résumé

In this paper we show that the contiguity and linearity of cographs on n vertices are both O(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 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
2013CrespelleGambetteTCS.pdf (493.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00915069 , version 1 (06-12-2013)

Identifiants

Citer

Christophe Crespelle, Philippe Gambette. (Nearly-)tight bounds on the contiguity and linearity of cographs. Theoretical Computer Science, 2014, 522, pp.1-12. ⟨10.1016/j.tcs.2013.11.036⟩. ⟨hal-00915069⟩
375 Consultations
229 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More