A lower bound for the interval number of a graph (Q788751)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A lower bound for the interval number of a graph |
scientific article |
Statements
A lower bound for the interval number of a graph (English)
0 references
1984
0 references
A family of sets \(I_ 1,I_ 2,...,I_ n\) with every \(I_ j\) being the union of at most m intervals of the real line is called and m-interval model of a graph G if G is the intersection graph of \(I_ 1,I_ 2,...,I_ n\). The lowest integer m for which G has an m-interval model is called interval number i(G) of G. In this paper, a lower bound for the interval number of a graph is presented. This is followed by the construction of graphs that are critical with respect to the interval number.
0 references
interval number
0 references
intersection graph
0 references
critical graphs
0 references