ON THE INDEPENDENCE AND CHROMATIC-NUMBERS OF RANDOM REGULAR GRAPHS

Let Gr denote a random r-regular graph with vertex set {1, 2, ..., n} and α(Gr) and χ(Gr) denote respectively its independence and chromatic numbers. We show that with probability going to 1 as n → ∞ respectively |δ(Gr) - 2n r(logr - log logr + 1 - log 2)|≤ γn r and |χ(Gr) - r 2 log r - 8r log logr (log)2| ≤ 8r log log r (log r)2 provided r = o(nθ), θ < 1 3, 0 < ε < 1, are constants, and r ≥ rε, where rε depends on ε only. © 1992.