Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13430546 | Electronic Notes in Theoretical Computer Science | 2019 | 19 Pages |
Abstract
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 I1,I2â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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
LÃvia Salgado Medeiros, Fabiano de Souza Oliveira, Jayme Luiz Szwarcfiter,