
doi: 10.1002/jgt.20005
AbstractThe interval number of a graph 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, denoted by i(G). Griggs and West showed that $i(G)\le \lceil {1\over 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. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 241–253, 2004
Extremal problems in graph theory, interval number, extremal graphs, Graph representations (geometric and intersection representations, etc.), graph representation, random graphs
Extremal problems in graph theory, interval number, extremal graphs, Graph representations (geometric and intersection representations, etc.), graph representation, random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
