| Popis: |
Let F be a family of intervals on the real line. An interval graph is the intersection graph of F . An interval order is a partial order ( F , ≺ ) such that for all I 1 , I 2 ∈ F , I1 ≺ I2 if and only if I1 lies entirely at the left of I2. Such a family F is called a model of the graph (order). The interval count of a given graph (resp. order) is the smallest number of interval lengths needed in any model of this graph (resp. order). The first problem we consider is related to the classes of graphs and orders which can be represented with two interval lengths, regarding to the inclusion hierarchy among such classes. The second problem is an extremal problem which consists of determining the smallest graph or order which has interval count at least k. In particular, we study a conjecture by Fishburn on this extremal problem, verifying its validity when such a conjecture is constrained to the classes of trivially perfect orders and split orders. |
Full Text from ScienceDirect