Lower bounds on the chromatic number of random graphs (Q2678448): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1007/s00493-021-4236-z / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00493-021-4236-Z / rank
 
Normal rank

Latest revision as of 17:10, 19 December 2024

scientific article
Language Label Description Also known as
English
Lower bounds on the chromatic number of random graphs
scientific article

    Statements

    Lower bounds on the chromatic number of random graphs (English)
    0 references
    0 references
    0 references
    0 references
    23 January 2023
    0 references
    A formula for lower bounds on the chromatic number \(\chi(G)\) of a random graph \(G\) is established using the so-called interpolation method from mathematical physics, see \textit{F. Guerra} and \textit{F. L. Toninelli} [Commun. Math. Phys. 230, No. 1, 71--79 (2002; Zbl 1004.82004)], instead of the second moment method. For random \(d\)-regular graphs, \(G(n,d)\), the formula is expressed algebraically, while for binomial random graphs (Erdős-Rényi) a variational formula is obtained. The formulas are then used to calculate explicit (and improved) lower bounds on \(\chi(G (n,d))\) with small \(d\) as well as binomial random graphs of small average degree. For large (average) degree it is shown how the new formulas can be used to easily re-derive asymptotic formulas without lengthy and complicated combinatorial arguments.
    0 references
    chromatic number
    0 references
    random graph
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers