##
**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 i_{d}(G) of a graph G with n vertices are presented. Theorem 1. The inequalities i(G) \geq n/4 lg_{2} n, i_{d}(G) \geq n/4d lg_{2} 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 K_{m,n}-free bipartite graphs with interval number at least c(m)· n^{1-2(m+1)}/lg_{2} n, which can be improved to \sqrt{n}/4+o(\sqrt{n}) for m = 2 and (n/2)^{2/3}/lg_{2} 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