## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  576.05019
Autor:  Erdös, Paul; West, Douglas B.
Title:  A note on the interval number of a graph. (In English)
Source:  Discrete Math. 55, 129-133 (1985).
Review:  Three results on the interval number i(G) and d-dimensional interval number id(G) of a graph G with n vertices are presented. Theorem 1. The inequalities i(G) \geq n/4 lg2 n, id(G) \geq n/4d lg2 n hold for almost every graph (i.e. the probability, that the lower bounds hold, goes to 1 as n ––> oo in the probability spaces containing all graphs on n vertices, each of them with the same probability). The first lower bound is also asymptotically true for almost every bipartite graph. Theorem 2. There exist Km,n-free bipartite graphs with interval number at least c(m)· n1-2(m+1)/lg2 n, which can be improved to \sqrt{n}/4+o(\sqrt{n}) for m = 2 and (n/2)2/3/lg2 n for m = 3. Theorem 3. There exist regular graphs of girth at least g with interval number at least ((n-1)/2)1/(g-2).
Reviewer:  M.Koman
Classif.:  * 05C10 Topological graph theory
60C05 Combinatorial probability
Keywords:  interval number; almost every graph; lower bounds; bipartite graphs; regular graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag