On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
From MaRDI portal
Publication:4256092
DOI<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
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
random graphshypergraphschromatic numbernibble methodchoice numberlocally sparse graphspolynomial coloring algorithm
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
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
