Almost all graphs with 2. 522\(n\) edges are not 3-colorable (Q1298442)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Almost all graphs with 2. 522\(n\) edges are not 3-colorable |
scientific article; zbMATH DE number 1326125
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Almost all graphs with 2. 522\(n\) edges are not 3-colorable |
scientific article; zbMATH DE number 1326125 |
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
