A note on the interval number of a graph
✍
Paul Erdös; Douglas B. West
📂
Article
📅
1985
🏛
Elsevier Science
🌐
English
⚖ 353 KB
Three results on the interval number of a graph on n vertices are presented. (1) The interval number of almost every graph is between n/4 Ig n and n/4 (this also holds for almost every bipartite graph). ( 2) There exist K+\_,, -free bipartite graphs with interval number at least c(m)n 1-2'Cm+1J/lg