On colouring random graphs
From MaRDI portal
Cites work
Cited in
(only showing first 100 items - show all)- Linear time self-stabilizing colorings
- A note on the chromatic number of a dense random graph
- The largest tree in a random graph
- Numerical experiences with graph coloring algorithms
- Randomized algorithms in combinatorial optimization: A survey
- On the order of the largest induced tree in a random graph
- Average polynomial time complexity of some NP-complete problems
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- Expose-and-merge exploration and the chromatic number of a random graph
- Patterns and invasions of evolutionarily stable strategies
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Degree sequences of random graphs
- Complexity of representation of graphs by set systems
- Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
- Chromatic optimisation: Limitations, objectives, uses, references
- On the independence and chromatic numbers of random regular graphs
- Limit theorems for complete subgraphs of random graphs
- Tree and forest weights and their application to nonuniform random graphs
- Expected complexity of graph partitioning problems
- Small maximal matchings in random graphs.
- A network-flow-based lower bound for the minimum weighted integer coloring problem
- Independence numbers of random sparse hypergraphs
- Dense subgraphs in random graphs
- Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
- Constraining the clustering transition for colorings of sparse random graphs
- On the chromatic forcing number of a random graph
- In search of the densest subgraph
- Potential energy principles in networked systems and their connections to optimization problems on graphs
- Random-cluster dynamics on random regular graphs in tree uniqueness
- The matching process and independent process in random regular graphs and hypergraphs
- Maximum sparse induced subgraphs of the binomial random graph with given number of edges
- Maximum induced forests in random graphs
- Cliques in rank-1 random graphs: the role of inhomogeneity
- The size of a maximum subgraph of the random graph with a given number of edges
- Maximum independent sets on random regular graphs
- Largest sparse subgraphs of random graphs
- Chromatic number versus chromatic number in graphs with bounded clique number
- On the concentration of the independence numbers of random hypergraphs
- On the independent set problem in random graphs
- Hadwiger's conjecture
- Largest sparse subgraphs of random graphs
- Coloring random graphs
- Minimum node covers and 2-bicritical graphs
- On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
- Parallel tempering for the planted clique problem
- Random instances of problems in NP -- algorithms and statistical physics
- The t-improper chromatic number of random graphs
- The \(t\)-improper chromatic number of random graphs
- Average-case complexity of backtrack search for coloring sparse random graphs
- Upper-bounding the k-colorability threshold by counting covers
- Complexity of coloring random graphs: an experimental study of the hardest region
- Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
- scientific article; zbMATH DE number 1863545 (Why is no real title available?)
- Pairwise disjoint maximal cliques in random graphs and sequential motion planning on random right angled Artin groups
- Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
- Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
- The Complexity of Public-Key Cryptography
- Sampling Strategies for Fast Updating of Gaussian Markov Random Fields
- On the connectivity of proper colorings of random graphs and hypergraphs
- Non-concentration of the chromatic number of a random graph
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- The chromatic number of random intersection graphs
- Separation choosability and dense bipartite induced subgraphs
- Superlogarithmic cliques in dense inhomogeneous random graphs
- Planting colourings silently
- Finding hidden cliques in linear time with high probability
- A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
- Decomposition of random graphs into complete bipartite graphs
- The chromatic number of random graphs
- 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
- Tight asymptotics of clique‐chromatic numbers of dense random graphs
- On the concentration of values of j-chromatic numbers of random hypergraphs
- A spectral algorithm for finding maximum cliques in dense random intersection 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
- Near-optimal dominating sets in dense random graphs in polynomial expected time
- On the concentration of the chromatic number of random graphs
- Greedy maximal independent sets via local limits
- Cryptography from planted graphs: security with logarithmic-size messages
- The largest hole in sparse random graphs
- The landscape of the planted clique problem: dense subgraphs and the overlap gap property
- Baby PIH: Parameterized inapproximability of min CSP
- Long induced paths in expanders
- The message complexity of distributed graph optimization
- Clique structure and other network properties of the tensor product of Erdős-Rényi graphs
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- Almost-linear planted cliques elude the Metropolis process
- Asymptotic optimality of degree-greedy discovering of independent sets in configuration model graphs
- Local convergence of random graph colorings
- Homomorphism complexes and \(k\)-cores
- Maximum induced trees and forests of bounded degree in random graphs
- Exact recovery of planted cliques in semi-random graphs
- Greedy approximation for the minimum connected dominating set with labeling
- An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
- Finding one community in a sparse graph
- On the chromatic number of random regular graphs
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
This page was built for publication: On colouring random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4050627)
