A lower bound for the interval number of a graph |
| |
Authors: | Christoph Maas |
| |
Affiliation: | Institut für Angewandte Mathematik, Universität Hamburg, 2000 Hamburg 13, Germany Fed. Rep. |
| |
Abstract: | The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I1,…,In with every Ii being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number. |
| |
Keywords: | Intersection graph interval number critical graph 05C99 |
本文献已被 ScienceDirect 等数据库收录! |