Speaker: Christophe Crespelle
Time: 9h30, Thursday, May 7, 2015
Location: Room 201, Building A5, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Ha Noi
Abstract: We will consider two graph parameters devoted to encoding: contiguity and linearity. These encodings are based on one (contiguity) or more (linearity) linear orders of the vertices of the graph G such that the set of neighbours of any vertex is a union of at most k intervals of these orders. The contiguity (or linearity) of G is the minimum k such that there exists such an encoding.
The linearity of a graph is always less than its contiguity but there is no obvious upper bound on the contiguity as an affine function of the linearity. In this talk we will show that, actually, such a bound does not exist. To that purpose we will consider the family of cographs, for which we will prove that the contiguity can be up to Omega(log n), while their linearity is always O(log n / log log n). We will also show that both of these bounds are tight by providing an equal upper or lower bound on the worst case. |
