Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434468 | Theoretical Computer Science | 2014 | 12 Pages |
Abstract
In this paper we show that the contiguity and linearity of cographs on n vertices are both O(logn). Moreover, we show that this bound is tight for contiguity as there exists a family of cographs on n vertices whose contiguity is Ω(logn). We also provide an Ω(logn/loglogn) 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christophe Crespelle, Philippe Gambette,