On the interval number of special graphs. (English) Zbl 1046.05039
Summary: The interval number of a graph \(G\), denoted by \(i(G)\), is the least natural number \(t\) such that \(G\) is the intersection graph of sets, each of which is the union of at most \(t\) intervals. J. R. Griggs and D. B. West [SIAM J. Algebraic Discrete Methods 1, 1–7 (1980; Zbl 0499.05033)] showed that \(i(G)\leq \lceil \frac{1}{2}(d+1)\rceil\). We describe the extremal graphs for that inequality when \(d\) is even. For three special perfect graph classes we give bounds on the interval number in terms of the independence number. Finally, we show that a graph needs to contain large complete bipartite induced subgraphs in order to have interval number larger than the random graph on the same number of vertices.
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
Citations:
Zbl 0499.05033References:
| [1] | Andreae, On the interval number of triangulated graph, J Graph Theory 3 pp 273– (1987) · Zbl 0652.05054 |
| [2] | Balogh, A sharp edge bound on the interval number of a graph, J Graph Theory 32 pp 153– (1999) · Zbl 0930.05067 |
| [3] | Balogh, On the interval number of dense graphs, Discrete Math 256 pp 423– (2002) · Zbl 1011.05032 · doi:10.1016/S0012-365X(01)00215-1 |
| [4] | A. Brandstädt V. B. Le J. P. Spinrad Graph classes: a survey, SIAM Monographs on Discrete Mathematics, and Applications, 3 1999 |
| [5] | Erdos, Ramsey-type theorems, Combinatorics and complexity (Chicago IL, 1987), Discrete Appl Math 25 pp 37– (1989) |
| [6] | Erdos, Probabilistic Methods in Combinatorics (1974) |
| [7] | Griggs, Extremal Values of the Interval Number of Graph, II, Discrete Math 28 pp 37– (1979) · Zbl 0446.05027 · doi:10.1016/0012-365X(79)90183-3 |
| [8] | Griggs, Extremal values of the interval number of graph, I, SIAM J Alg Discrete Meth 1 pp 1– (1980) |
| [9] | Hopkins, The interval number of a complete multipartite graph, Discrete Applied Math 8 pp 163– (1984) · Zbl 0537.05061 · doi:10.1016/0166-218X(84)90099-4 |
| [10] | Kovári, On a problem of K. Zarankiewicz, Colloq Math 3 pp 50– (1954) |
| [11] | Pluhár, Remarks on the interval number of graphs, Acta Cybernetica 12 pp 125– (1995) · Zbl 0840.68092 |
| [12] | Scheinerman, The maximum interval number of graphs with given genus, J Graph Theory 3 pp 441– (1987) · Zbl 0652.05026 |
| [13] | Scheinerman, On the interval number of a chordal graph, J Graph Theory 12 pp 311– (1988) · Zbl 0647.05058 |
| [14] | Scheinerman, On the interval number of random graphs, Discrete Math 82 pp 105– (1990) · Zbl 0712.05049 · doi:10.1016/0012-365X(90)90050-R |
| [15] | Scheinerman, The interval number of a planar graph: Three intervals suffice, J Combin Theory B 35 pp 224– (1985) · Zbl 0528.05053 |
| [16] | Spinrad, An improved edge bound on the interval number of a graph, J Graph Theory 3 pp 447– (1987) · Zbl 0653.05058 |
| [17] | Trotter, On double and multiple interval graphs, J Graph Theory 3 pp 205– (1979) · Zbl 0417.05050 |
| [18] | West, A short proof of the degree bound on interval number, Discrete Math 73 pp 307– (1989) · Zbl 0663.05040 · doi:10.1016/0012-365X(89)90276-8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
