List coloring of random and pseudo-random graphs (Q1977428): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Import241208061232 (talk | contribs)
Normalize DOI.
 
(One intermediate revision by one other user not shown)
Property / DOI
 
Property / DOI: 10.1007/s004939970001 / rank
Normal 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
    0 references
    0 references
    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

    Identifiers