Thời gian: 9h30 Thứ 5, 7/5/2015

Địa điểm: Phòng 201, Nhà A5, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy Hà Nội

Tóm tắt: 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.