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