On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1097-0118(199907)31:3<201::AID-JGT5>3.0.CO;2-T" /><201::AID-JGT5>3.0.CO;2-T 10.1002/(SICI)1097-0118(199907)31:3<201::AID-JGT5>3.0.CO;2-TzbMath0928.05025OpenAlexW4249811006MaRDI QIDQ4256092

Van H. Vu

Publication date: 9 January 2000

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199907)31:3<201::aid-jgt5>3.0.co;2-t

zbMATH Keywords

random graphshypergraphschromatic numbernibble methodchoice numberlocally sparse graphspolynomial coloring algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Concentration of non‐Lipschitz functions and applications ⋮ On-line list colouring of random graphs ⋮ Random regular graphs of high degree ⋮ New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help ⋮ On the concentration of multivariate polynomials with small expectation ⋮ The strong chromatic index ofC4-free graphs ⋮ On a refinement of Waring's problem ⋮ Choosability in random hypergraphs

Cites Work

• Coloring graphs with sparse neighborhoods
• List coloring of random and pseudo-random graphs
• On Brooks' Theorem for Sparse Graphs

This page was built for publication: On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs