List coloring of random and pseudo-random graphs (Q1977428): Difference between revisions
From MaRDI portal
Set profile property. |
Normalize DOI. |
||
(One intermediate revision by one other user not shown) | |||
Property / DOI | |||
Property / DOI: 10.1007/s004939970001 / rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004939970001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2038200513 / rank | |||
Normal rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S004939970001 / rank | |||
Normal rank |
Latest revision as of 16:04, 16 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | List coloring of random and pseudo-random graphs |
scientific article |
Statements
List coloring of random and pseudo-random graphs (English)
0 references
14 May 2000
0 references
The choice number of a graph \(G\) is the least \(k\) such that whenever a \(k\)-set of colors is assigned to every vertex of \(G\) then there is a good coloring of \(G\) that assigns to each vertex a color from its color set. It is shown that the choice number of the random graph \(G\bigl(n,p(n)\bigr)\) is a.s. \(\Theta \bigl(np(n)/\log\bigl(np(n)\bigr)\bigr)\) if \(2<np(n)\leq n/2\). A bound for the chromatic number of regular graphs is given in terms of the two largest eigenvalues. Finally, it is conjectured that if \(np(n)\to\infty\) then the choice number and the chromatic number of \(G\bigl(n,p(n)\bigr)\) are asymptotically equal.
0 references
random graphs
0 references
chromatic number
0 references