The chromatic number of random graphs
From MaRDI portal
Publication:5905438
DOI10.1007/BF01375472zbMath0771.05090WikidataQ93437489 ScholiaQ93437489MaRDI QIDQ5905438
Publication date: 27 June 1992
Published in: Combinatorica (Search for Journal in Brave)
Related Items
Phase transitions in discrete structures, Sandwiching random graphs: universality between random graph models, An improved algorithm for approximating the chromatic number of \(G_{n,p}\), On the strong chromatic number of random hypergraphs, Colouring Non-sparse Random Intersection Graphs, The set chromatic number of random graphs, On Some Combinatorial Properties of Random Intersection Graphs, Information-theoretic thresholds from the cavity method, Independence numbers and chromatic numbers of the random subgraphs of some distance graphs, Concentration of measure and isoperimetric inequalities in product spaces, Unnamed Item, On the standard \((2,2)\)-conjecture, Complexity of Coloring Random Graphs, On the concentration of the chromatic number of a random hypergraph, Counterexamples to a Conjecture of Harris on Hall Ratio, Average-case complexity of backtrack search for coloring sparse random graphs, Estimating the \(r\)-colorability threshold for a random hypergraph, Upper-bounding the \(k\)-colorability threshold by counting covers, Lower bounds on the chromatic number of random graphs, The t-improper chromatic number of random graphs, On the chromatic number of random regular graphs, On the concentration of values of \(j\)-chromatic numbers of random hypergraphs, On the chromatic number in the stochastic block model, How does the chromatic number of a random graph vary?, On the independence number and the chromatic number of generalized preferential attachment models, On the concentration of the chromatic number of random graphs, Estimating the strong \(r\)-colorability threshold in random hypergraphs, Planting Colourings Silently, Gibbs states and the set of solutions of random constraint satisfaction problems, On the strong chromatic number of a random 3-uniform hypergraph, On the chromatic number of random geometric graphs, Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs, The minrank of random graphs, The game chromatic number of dense random graphs, On-line list colouring of random graphs, The t-Improper Chromatic Number of Random Graphs, Sparse multipartite graphs as partition universal for graphs with bounded degree, On the chromatic number of random graphs, Random regular graphs of high degree, On the chromatic number of non-sparse random intersection graphs, The chromatic number of random intersection graphs, Indicated coloring of graphs, Why almost all \(k\)-colorable graphs are easy to color, On the tractability of coloring semirandom graphs, Equitable coloring of random graphs, On the Chromatic Number of Random Graphs with a Fixed Degree Sequence, Local convergence of random graph colorings, Local resilience of graphs, Colorings of partial Steiner systems and their applications, Generalized chromatic numbers of random graphs, Approximating the minimum independent dominating set in perturbed graphs, On the Number of Solutions in Random Graphk-Colouring, An incremental search heuristic for coloring vertices of a graph, Separation Choosability and Dense Bipartite Induced Subgraphs, Approximability Distance in the Space of H-Colourability Problems, A note on the chromatic number of a dense random graph, The concentration of the chromatic number of random graphs, Coloring Random Graphs, On the chromatic number of random \(d\)-regular graphs, Random regular graphs of non-constant degree: concentration of the chromatic number, Cliques and chromatic number in multiregime random graphs, On the Concentration of the Domination Number of the Random Graph, On the Chromatic Index of Random Uniform Hypergraphs, Deciding \(k\)-colorability in expected polynomial time, Choosability in random hypergraphs, Graph imperfection. II, The chromatic discrepancy of graphs, The resolution complexity of random graph \(k\)-colorability, New upper bound for the chromatic number of a random subgraph of a distance graph
Cites Work
