Back
On the independence and chromatic numbers of random regular graphs
Authors:
- A.M Frieze,
- Tomasz Łuczak
Abstract
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.
- Record ID
- UAMe1a642827dce468e9d233468f06132b2
- Author
- Journal series
- Journal of Combinatorial Theory Series B, ISSN 0095-8956
- Issue year
- 1992
- Vol
- 54
- No
- 1
- Pages
- 123-132
- ASJC Classification
- ; ;
- DOI
- DOI:10.1016/0095-8956(92)90070-E Opening in a new tab
- URL
- https://www.sciencedirect.com/science/article/pii/009589569290070E?via%3Dihub Opening in a new tab
- Language
- (en) English
- File
-
- File: 1
- 1-s2.0-009589569290070E-main.pdf
-
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 48; = 48; = 95; : 1999 = 1.627; : 2006 (2 years) = 0.792 - 2007 (5 years) =0.927
- Citation count
- 95
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAMe1a642827dce468e9d233468f06132b2/
- URN
urn:amu-prod:UAMe1a642827dce468e9d233468f06132b2
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.