On colouring random graphs

DOI10.1017/S0305004100051124zbMath0297.05112OpenAlexW2112575355WikidataQ56852736 ScholiaQ56852736MaRDI QIDQ4050627

Geoffrey R. Grimmett, Colin J. H. McDiarmid

Publication date: 1975

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0305004100051124

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (90)

Randomized algorithms in combinatorial optimization: A survey ⋮ Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ Greedy approximation for the minimum connected dominating set with labeling ⋮ Coloring random graphs ⋮ On the order of the largest induced tree in a random graph ⋮ Average polynomial time complexity of some NP-complete problems ⋮ On independent sets in random graphs ⋮ Expected complexity of graph partitioning problems ⋮ Sharp concentration of the chromatic number on random graphs \(G_{n,p}\) ⋮ Sampling Strategies for Fast Updating of Gaussian Markov Random Fields ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Chromatic number versus chromatic number in graphs with bounded clique number ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Expose-and-merge exploration and the chromatic number of a random graph ⋮ Patterns and invasions of evolutionarily stable strategies ⋮ Maximum independent sets on random regular graphs ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ The largest hole in sparse random graphs ⋮ Which networks permit stable allocations? A theory of network‐based comparisons ⋮ Finding one community in a sparse graph ⋮ Tight asymptotics of clique‐chromatic numbers of dense random graphs ⋮ Fast probabilistic algorithms for Hamiltonian circuits and matchings ⋮ The t-improper chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time ⋮ On the concentration of values of \(j\)-chromatic numbers of random hypergraphs ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ Independence numbers of random sparse hypergraphs ⋮ Small maximal matchings in random graphs. ⋮ Degree sequences of random graphs ⋮ How does the chromatic number of a random graph vary? ⋮ Coloring k-colorable graphs in constant expected parallel time ⋮ Tight concentration of star saturation number in random graphs ⋮ On the concentration of the independence numbers of random hypergraphs ⋮ Near-optimal dominating sets in dense random graphs in polynomial expected time ⋮ On the concentration of the chromatic number of random graphs ⋮ Planting Colourings Silently ⋮ Complexity of representation of graphs by set systems ⋮ Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations ⋮ Chromatic optimisation: Limitations, objectives, uses, references ⋮ Maximum sparse induced subgraphs of the binomial random graph with given number of edges ⋮ On the connectivity of proper colorings of random graphs and hypergraphs ⋮ On the independence number of random graphs ⋮ Non-concentration of the chromatic number of a random graph ⋮ Parallel tempering for the planted clique problem ⋮ On the independence and chromatic numbers of random regular graphs ⋮ Maximum induced forests in random graphs ⋮ Dense subgraphs in random graphs ⋮ The t-Improper Chromatic Number of Random Graphs ⋮ Unnamed Item ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Constraining the clustering transition for colorings of sparse random graphs ⋮ The chromatic number of random intersection graphs ⋮ The chromatic number of random graphs ⋮ In search of the densest subgraph ⋮ Unnamed Item ⋮ Decomposition of Random Graphs into Complete Bipartite Graphs ⋮ Potential energy principles in networked systems and their connections to optimization problems on graphs ⋮ Minimum node covers and 2-bicritical graphs ⋮ Cliques in rank-1 random graphs: the role of inhomogeneity ⋮ Local convergence of random graph colorings ⋮ Homomorphism complexes and \(k\)-cores ⋮ Largest sparse subgraphs of random graphs ⋮ On the independent set problem in random graphs ⋮ Limit theorems for complete subgraphs of random graphs ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups ⋮ Linear time self-stabilizing colorings ⋮ Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms ⋮ The size of a maximum subgraph of the random graph with a given number of edges ⋮ Separation Choosability and Dense Bipartite Induced Subgraphs ⋮ A note on the chromatic number of a dense random graph ⋮ Hadwiger’s Conjecture ⋮ Superlogarithmic Cliques in Dense Inhomogeneous Random Graphs ⋮ On the chromatic forcing number of a random graph ⋮ Tree and forest weights and their application to nonuniform random graphs ⋮ The largest tree in a random graph ⋮ Optimal approximation of sparse hessians and its equivalence to a graph coloring problem ⋮ A network-flow-based lower bound for the minimum weighted integer coloring problem ⋮ Unnamed Item ⋮ Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model ⋮ The Complexity of Public-Key Cryptography ⋮ The matching process and independent process in random regular graphs and hypergraphs ⋮ Numerical experiences with graph coloring algorithms

Cites Work

• The Eigenvalues of a Graph and Its Chromatic Number
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Unnamed Item

This page was built for publication: On colouring random graphs