On colouring random graphs
From MaRDI portal
Publication:4050627
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
Related Items
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
