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...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Pluhár András
Dokumentumtípus: Cikk
Megjelent: 1995
Sorozat:Acta cybernetica 12 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12549
Leíró adatok
Tartalmi kivonat: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.
Terjedelem/Fizikai jellemzők:125-129
ISSN:0324-721X