Almost all graphs with 2. 522\(n\) edges are not 3-colorable (Q1298442): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 11:00, 31 January 2024
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
