Coloring complete bipartite graphs from random lists

DOI10.1002/rsa.20114zbMath1110.05035arXivmath/0512010OpenAlexW4238443289MaRDI QIDQ3419602

Michael Krivelevich, Asaf Nachmias

Publication date: 7 February 2007

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0512010

zbMATH Keywords

asymptotic probability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (12)

The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes ⋮ Large complete minors in random subgraphs ⋮ Coloring complete and complete bipartite graphs from random lists ⋮ The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property ⋮ Proportional choosability of complete bipartite graphs ⋮ Smoothed Analysis on Connected Graphs ⋮ A Poisson Approximation for an Occupancy Problem with Collisions ⋮ Coloring graphs from random lists of size 2 ⋮ Coloring graphs from random lists of fixed size ⋮ Vertex coloring complete multipartite graphs from random lists of size 2 ⋮ Isoperimetric numbers of randomly perturbed intersection graphs ⋮ Expansion in supercritical random subgraphs of the hypercube and its consequences

Cites Work

• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

This page was built for publication: Coloring complete bipartite graphs from random lists