The chromatic number of random graphs
From MaRDI portal
Publication:5903892
DOI10.1007/BF02122551zbMath0666.05033OpenAlexW2082249316WikidataQ93437532 ScholiaQ93437532MaRDI QIDQ5903892
Publication date: 1988
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02122551
Related Items
Phase transitions in discrete structures, Acyclic subgraphs with high chromatic number, Coloring random graphs, Random lifts of graphs: Independence and chromatic number, Sandwiching random graphs: universality between random graph models, Graph clustering via generalized colorings, Trees contained in every orientation of a graph, Expected complexity of graph partitioning problems, An improved algorithm for approximating the chromatic number of \(G_{n,p}\), Colouring Non-sparse Random Intersection Graphs, Chromatic number versus chromatic number in graphs with bounded clique number, 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, Choice Numbers of Graphs: a Probabilistic Approach, Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck, For most graphs H , most H -free graphs have a linear homogeneous set, Unnamed Item, The stable set problem: clique and nodal inequalities revisited, Complexity of Coloring Random Graphs, On the concentration of the chromatic number of a random hypergraph, On Two Limit Values of the Chromatic Number of a Random Hypergraph, On the probability of nonexistence in binomial subsets, Average-case complexity of backtrack search for coloring sparse random graphs, Complete acyclic colorings, Estimating the \(r\)-colorability threshold for a random hypergraph, Upper-bounding the \(k\)-colorability threshold by counting covers, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, 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, Random I‐colorable graphs, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), Upper bound on cubicity in terms of boxicity for graphs of low chromatic number, On the independence number and the chromatic number of generalized preferential attachment models, Online sum-paintability: the slow-coloring game, On the Method of Typical Bounded Differences, On the Chromatic Number of Random Cayley Graphs, Planting Colourings Silently, Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz, On the strong chromatic number of a random 3-uniform hypergraph, Holes in random graphs, Two notions of unit distance 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, Non-concentration of the chromatic number of a random graph, On-line list colouring of random graphs, On the independence and chromatic numbers of random regular graphs, The t-Improper Chromatic Number of Random Graphs, On the chromatic number of random graphs, Algebraic properties of chromatic roots, Colorings of spaces, and random graphs, Random regular graphs of high degree, The total interval number of a graph. I: Fundamental classes, On the chromatic number of non-sparse random intersection graphs, Excluding induced subgraphs. II: Extremal graphs, The chromatic number of random intersection graphs, Uncertain vertex coloring problem, Indicated coloring of graphs, Why almost all \(k\)-colorable graphs are easy to color, On the tractability of coloring semirandom graphs, Hadwiger numbers and over-dominating colourings, Equitable coloring of random graphs, Unnamed Item, Local convergence of random graph colorings, Local resilience of graphs, On threshold probability for the stability of independent sets in distance graphs, On the chromatic number of the preferential attachment graph, Colorings of partial Steiner systems and their applications, Generalized chromatic numbers of random graphs, Around Borsuk's hypothesis, Dold's theorem from viewpoint of strong compatibility graphs, Approximating the minimum independent dominating set in perturbed graphs, On the Number of Solutions in Random Graphk-Colouring, The minrank of random graphs over arbitrary fields, Separation Choosability and Dense Bipartite Induced Subgraphs, Approximability Distance in the Space of H-Colourability Problems, Some results on \((a:b)\)-choosability, A note on the chromatic number of a dense random graph, The plane-width of graphs, Clique numbers of random subgraphs of some distance graphs, The concentration of the chromatic number of random graphs, Parallel graph algorithms that are efficients on average, Bounding the strong chromatic index of dense random graphs, On the chromatic number of random subgraphs of a certain distance graph, Sharp concentration of the equitable chromatic number of dense 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 Plane-Width of Graphs, The probability method: Successes and limitations, On the Chromatic Index of Random Uniform Hypergraphs, Deciding \(k\)-colorability in expected polynomial time, Choosability in random hypergraphs, Graph imperfection. II, Isoperimetric inequalities and fractional set systems, Lattice bandwidth of random graphs, New upper bound for the chromatic number of a random subgraph of a distance graph, Fractional cocoloring of graphs, On Induced Paths, Holes, and Trees in Random Graphs, On the edit distance function of the random graph, The largest hole in sparse random graphs, Tight asymptotics of clique‐chromatic numbers of dense random graphs, On the concentration of values of \(j\)-chromatic numbers of random hypergraphs, On the chromatic number in the stochastic block model, Large deviations in random latin squares, How does the chromatic number of a random graph vary?, Coloring k-colorable graphs in constant expected parallel time, Experimental study of semi-supervised graph 2-clustering problem, On the concentration of the chromatic number of random graphs, The chromatic number of random graphs, On the Chromatic Number of Random Graphs with a Fixed Degree Sequence, Triangulations and the Hajós conjecture, On the Concentration of the Domination Number of the Random Graph, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles, Ramsey numbers of cycles versus general graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- Expose-and-merge exploration and the chromatic number of a random graph
- Random embeddings of Euclidean spaces in sequence spaces
- On tail probabilities for martingales
- On the chromatic forcing number of a random graph
- Weighted sums of certain dependent random variables
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
- On colouring random graphs
- Cliques in random graphs
- On the Dimension of the l n p -Subspaces of Banach Spaces, for 1 p < 2
