Determining the interval number of a triangle-free graph
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.