Remarks on the interval number of graphs

The interval number of a graph G is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we propose a family of representations for the graph G, which yield the well-known upper bound [1)] , where d is the maximum degree of...

Full description

Saved in:
Bibliographic Details
Main Author: Pluhár András
Format: Article
Published: 1995
Series:Acta cybernetica 12 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Subjects:
Online Access:http://acta.bibl.u-szeged.hu/12549
Description
Summary:The interval number of a graph G is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we propose a family of representations for the graph G, which yield the well-known upper bound [1)] , where d is the maximum degree of G. The extremal graphs for even d are also described, and the upper bound on the interval number in terms of the number of edges of G is improved.
Physical Description:125-129
ISSN:0324-721X