Remarks on the interval number of graphs

Pluhár András: Remarks on the interval number of graphs. In: Acta cybernetica, (12) 2. pp. 125-129. (1995)

[thumbnail of cybernetica_012_numb_002_125-129.pdf]
Cikk, tanulmány, mű

Download (367kB) | Preview


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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1995
Volume: 12
Number: 2
ISSN: 0324-721X
Page Range: pp. 125-129
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 129. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 13:39

Actions (login required)

View Item View Item