(Nearly-)tight bounds on the contiguity and linearity of cographs - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2014

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

Abstract

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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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 View
229 Download

Altmetric

Share

Gmail Facebook X LinkedIn More