Properties of integer-interval graphs. (English) Zbl 0646.05054
Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 48, 145-151 (1985).
[For the entire collection see Zbl 0619.00006.]
The integer-interval graph on [0,n], for \(n\in {\mathbb{Z}}\), \(n>0\), is the graph \(G_ n=(V,E)\) defined as follows: for all a,b\(\in {\mathbb{Z}}\), \(0\leq a<b\leq n\), there is a vertex \(v\in V\) corresponding to the closed interval [a,b] and the vertices corresponding to [a,b] and [c,d] are adjacent if [a,b]\(\cap [c,d]\neq \emptyset.\)
For such a graph \(G_ n=(V,E)\), the author proves that: \((i)\quad E=(1/12)(n-1)n(n+1)(n+4);\) (ii) the clique number is \(\omega_ n=n^ 2/4+n+(-1)\quad n/8-1/8;\) (iii) the chromatic number is given by: n \(2/4+n\) for n even and n \(2/4+n-1/4\) for n odd.
The integer-interval graph on [0,n], for \(n\in {\mathbb{Z}}\), \(n>0\), is the graph \(G_ n=(V,E)\) defined as follows: for all a,b\(\in {\mathbb{Z}}\), \(0\leq a<b\leq n\), there is a vertex \(v\in V\) corresponding to the closed interval [a,b] and the vertices corresponding to [a,b] and [c,d] are adjacent if [a,b]\(\cap [c,d]\neq \emptyset.\)
For such a graph \(G_ n=(V,E)\), the author proves that: \((i)\quad E=(1/12)(n-1)n(n+1)(n+4);\) (ii) the clique number is \(\omega_ n=n^ 2/4+n+(-1)\quad n/8-1/8;\) (iii) the chromatic number is given by: n \(2/4+n\) for n even and n \(2/4+n-1/4\) for n odd.
MSC:
| 05C75 | Structural characterization of families of graphs |
