Determining the interval number of a triangle-free graph

Computing - Tập 31 - Trang 347-354 - 1983
C. Maas1
1Institut für Angewandte Mathematik, Universität Hamburg, Hamburg 13, Federal Republic of Germany

Tóm tắt

The interval numberi (G) of a graphG withn vertices is the lowest integerm such thatG is the intersection graph of some family of setsI 1, ...,I n with everyI i being the union of at mostm real intervals. In this article, an idea is presented for the algorithmic determination ofi (G), ifG is triangle-free. An example for the application of these considerations is given.

Tài liệu tham khảo