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.
Tài liệu tham khảo
Golumbic, M. C.: Algorithmic graph theory and perfect graphs. New York-London: Academic Press 1980.
Griggs, J. R.: Extremal values of the interval number of a graph II. Disc. Math.28, 37–47 (1979).
Griggs, J. R., West, D. B.: Extremal values of the interval number of a graph. SIAM J. Alg. Disc. Meth.1, 1–7 (1980).
Maas, C.: Some results about the interval number of a graph. Discrete Applied Mathematics6, 99–102 (1983).
Maas, C.: A lower bound for the interval number of a graph. (To appear.)
Roberts, F. S.: Discrete mathematical models. Englewood Cliffs, N. J.: Prentice-Hall 1976.
Trotter, W. T., Harary, F.: On double and multiple interval graphs. J. Graph Theory3, 205–211 (1979).