The interval number of a complete multipartite graph (Q792347): Difference between revisions

A graph is called a t-interval graph if it is the intersection graph of a family of subsets of the real line such that each subset is the union of at most t closed intervals. the interval number of a graph G is the least positive integer t for which G is a t-interval graph. Interval numbers \(i(n_ 1,...,n_ p)\) are determined for all complete multipartite graphs \(K(n_ 1,...,n_ p).\) It is shown that \(i(n_ 1,...,n_ p)=i(n_ 1,n_ 2)\) for \(p\geq 3\) and \(n_ 1\geq n_ 2\geq...\geq n_ p\) unless \((n_ 1,n_ 2)=(7,5)\) or \((n_ 1,n_ 2)=(n^ 2-n-1,n)\) for \(n\geq 3\). In the exceptional cases \(i(n_ 1,...,n_ p)=1+i(n_ 1,n_ 2).\)