The chromatic number of random graphs

An asymptotic concentration interval is given for the chromatic number of a Bernoulli graph \(G(n,p)\) when \(np\) is sufficiently large and \(p\to 0\).

Recommendations

The chromatic number of random graphs
On the Chromatic Number of Random Graphs
On the chromatic number of random graphs
On the chromatic number of random graphs
The chromatic number of random regular graphs
scientific article; zbMATH DE number 1380583
The set chromatic number of random graphs
On the chromatic number of random regular graphs
Generalized chromatic numbers of random graphs

Cites work

Expose-and-merge exploration and the chromatic number of a random graph
On the independence number of random graphs
Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
The chromatic number of random graphs

Cited in

(78)

A note on the chromatic number of a dense random graph
On the chromatic number of random \(d\)-regular graphs
Random regular graphs of non-constant degree: concentration of the chromatic number
The concentration of the chromatic number of random graphs
Phase transitions in discrete structures
Chromatic number of random Kneser hypergraphs
Sparse multipartite graphs as partition universal for graphs with bounded degree
Indicated coloring of graphs
Deciding \(k\)-colorability in expected polynomial time
Choosability in random hypergraphs
Graph imperfection. II
Sandwiching random graphs: universality between random graph models
Concentration of measure and isoperimetric inequalities in product spaces
Distinguishing chromatic number of random Cayley graphs
An incremental search heuristic for coloring vertices of a graph
Cliques and chromatic number in multiregime random graphs
On the strong chromatic number of random hypergraphs
Estimating the r-colorability threshold for a random hypergraph
On the independence number and the chromatic number of generalized preferential attachment models
On the strong chromatic number of a random 3-uniform hypergraph
The chromatic discrepancy of graphs
New upper bound for the chromatic number of a random subgraph of a distance graph
On the concentration of the chromatic number of a random hypergraph
Colorings of partial Steiner systems and their applications
The resolution complexity of random graph \(k\)-colorability
On the standard (2,2)-conjecture
Lower bounds on the chromatic number of random graphs
Estimating the strong r-colorability threshold in random hypergraphs
Random regular graphs of high degree
Coloring random graphs
On the game chromatic number of sparse random graphs
Equitable coloring of random graphs
Colouring Non-sparse Random Intersection Graphs
The set chromatic number of random graphs
Approximability Distance in the Space of H-Colourability Problems
On Some Combinatorial Properties of Random Intersection Graphs
Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
The t-improper chromatic number of random graphs
On the strong chromatic number of random graphs
The \(t\)-improper chromatic number of random graphs
Local resilience of 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
Generalized chromatic numbers of random graphs
scientific article; zbMATH DE number 1380613 (Why is no real title available?)
Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
The game chromatic number of dense random graphs
On-line list colouring of random graphs
The minrank of random graphs
Fractional chromatic number of a random subgraph
Counterexamples to a Conjecture of Harris on Hall Ratio
On the chromatic number of non-sparse random intersection graphs
The chromatic number of random intersection graphs
On the number of solutions in random graph \(k\)-colouring
Separation choosability and dense bipartite induced subgraphs
On the chromatic index of random uniform hypergraphs
Chromatic thresholds in sparse random graphs
Planting colourings silently
Gibbs states and the set of solutions of random constraint satisfaction problems
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
The game chromatic number of random graphs
On the concentration of the domination number of the random graph
The two possible values of the chromatic number of a random graph
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 concentration of the chromatic number of random graphs
Two values of the chromatic number of a sparse random graph
On the chromatic number of random geometric graphs
The fractional chromatic number of random graphs
Local convergence of random graph colorings
Approximating the minimum independent dominating set in perturbed graphs
An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
On the chromatic number of random regular graphs
On the chromatic number of random graphs
Why almost all k-colorable graphs are easy to color
On the tractability of coloring semirandom graphs

This page was built for publication: The chromatic number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5905438)