The interval number of a complete multipartite graph
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).\)
- On an extremal problem concerning the interval number of a graph
- Irredundancy in multiple interval representations
- The total interval number of a graph
- On the unit interval number of a graph
- Interval numbers of powers of block graphs
- Total interval numbers of complete \(r\)-partite graphs
- scientific article; zbMATH DE number 4181392 (Why is no real title available?)
- scientific article; zbMATH DE number 1185295 (Why is no real title available?)
- scientific article; zbMATH DE number 1011262 (Why is no real title available?)
- scientific article; zbMATH DE number 1472165 (Why is no real title available?)
- On the interval number of special graphs
- The Total Interval Number of a Graph II: Trees and Complexity
- scientific article; zbMATH DE number 894698 (Why is no real title available?)
- Recognizing graphs with fixed interval number is NP-complete
- The interval number of a planar graph: Three intervals suffice
- Some results about the interval number of a graph
- A lower bound for the interval number of a graph
- On the interval number of random graphs
This page was built for publication: The interval number of a complete multipartite graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792347)
