Almost all graphs with 2. 522\(n\) edges are not 3-colorable (Q1298442)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Almost all graphs with 2. 522\(n\) edges are not 3-colorable |
scientific article |
Statements
Almost all graphs with 2. 522\(n\) edges are not 3-colorable (English)
0 references
22 August 1999
0 references
Summary: We prove that for \(c \geq 2.522\) a random graph with \(n\) vertices and \(m=cn\) edges is not 3-colorable with probability \(1-o(1)\). Similar bounds for non-\(k\)-colorability are given for \(k>3\).
0 references
