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

Christophe Crespelle 1 Philippe Gambette 2
1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
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.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00915069
Contributor : Philippe Gambette <>
Submitted on : Friday, December 6, 2013 - 3:00:49 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Long-term archiving on : Friday, March 7, 2014 - 7:45:12 AM

File

2013CrespelleGambetteTCS.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

804

Files downloads

269