Coloring complete bipartite graphs from random lists

DOI10.1002/rsa.20114zbMath1110.05035arXivmath/0512010MaRDI 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

05C80: Random graphs (graph-theoretic aspects)

05C65: Hypergraphs

60C05: Combinatorial probability

05C15: Coloring of graphs and hypergraphs

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

Related Items

The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property, Coloring graphs from random lists of fixed size, 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, Vertex coloring complete multipartite graphs from random lists of size 2, Coloring graphs from random lists of size 2, Expansion in supercritical random subgraphs of the hypercube and its consequences, Isoperimetric numbers of randomly perturbed intersection graphs, Proportional choosability of complete bipartite graphs, Smoothed Analysis on Connected Graphs, A Poisson Approximation for an Occupancy Problem with Collisions

Cites Work

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