Graph Colouring and the Probabilistic Method

By Bruce A. Reed. 2001

554 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/a383db167c0b028d3aeeb117b8478ec9ae53eb0a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lovász Local Lemma (2003, background): “ncy graph”. The Lov´asz local lemma (and its algorithmic versions [8, 3]) has found a signiﬁcant variety of applications, especially in graph coloring, Ramsey theory, and related algorithmic problems [2, 23, 83]. In this paper we would like to elucidate the close relation between these two apparentl”
On the average size of independent sets in triangle-free graphs (2016, methodology): “f graphs of average degree d in which neighborhoods are r-colorable. Alon and Spencer [4] used this technique to give a result like Theorem 1 but with a worse constant. See also chapters 21 and 22 of [19] for an exposition of some of these results, and [18] for a recent application to hypergraphs. U”
The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “ about it should either read the original papers of Erd˝os, e.g., [61], [62], Erd˝os and R´enyi, e.g., [84], or some books, e.g., Bollobas, [27], Janson, L uczak and Rucin´ski, [149], Molloy and Reed [192]. Theorem 2.26 (Erd˝os-R´enyi First Moment method). Let L = {L 1,...,Lt} be a family of graphs,”
Topological lower bounds for the chromatic number: A hierarchy (2002, methodology): “(See [9] for implementations, and Reed & Molloy [28] for a theoretical study of randomized algorithms.”
On concentration of self-bounding functions (2009, background): “McDiarmid and Reed further generalize the notion of self-bounding functions.”