A Note on the Unit Interval Number and Proper Interval Number of Graphs

A. Raychaudhuri1
1The College of Staten Island Department of Mathematics 2800 Victory Boulevard Staten Island, New York 10314

Abstract

In this paper, we study intersection assignments of graphs using multiple intervals for each vertex, where each interval is of identical length or in which no interval is properly contained in another. The resulting parameters unit interval number, \(i_u(G)\) and proper interval number, \(i_p(G)\) are shown to be equal for any graph \(G\). Also, \(i_u(G)\) of a triangle-free graph \(G\) with maximum degree \(D\) is \(\left\lceil\frac{D+1}{2}\right\rceil\) if \(G\) is regular and \(\left\lceil\frac{D}{2}\right\rceil\) otherwise.