Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs

DOI10.1134/S1064562414050147MaRDI QIDQ483670zbMATH OpenFDO

Authors L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, Andrei M. Raigorodskii

Publication date 17 December 2014

Published in Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

random graphchromatic numberindependence number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Independence numbers of random subgraphs of distance graphs
• Independence numbers of random subgraphs of some distance graph
• On the chromatic number of random subgraphs of a certain distance graph
• Independence numbers of random subgraphs of a distance graph

Cites work

• scientific article; zbMATH DE number 5122787 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring distance graphs and graphs of diameters
• Excursions into combinatorial geometry
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• Random graphs.
• Research Problems in Discrete Geometry
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• The chromatic number of random graphs
• The chromatic number of random graphs

Cited in

(24)

• On the stability of some Erdős-Ko-Rado type results
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• On random subgraphs of Kneser and Schrijver graphs
• Chromatic number of random Kneser hypergraphs
• On threshold probability for the stability of independent sets in distance graphs
• On the random version of the Erdős matching conjecture
• Sharp bounds for the chromatic number of random Kneser graphs
• Independence numbers of random subgraphs of a distance graph
• Diameters of random distance graphs
• Independence numbers of random subgraphs of distance graphs
• New upper bound for the chromatic number of a random subgraph of a distance graph
• Hamiltonian paths in distance graphs
• On the number of edges in induced subgraphs of a special distance graph
• A new estimate for the number of edges in induced subgraphs of a special distance graph
• On the stability of the independence number of a random subgraph
• Sharp bounds for the chromatic number of random Kneser graphs
• On the stability of the Erdös-Ko-Rado theorem
• Independence numbers of random subgraphs of some distance graph
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• On random subgraphs of Kneser graphs and their generalizations
• Random Kneser graphs and hypergraphs
• On the chromatic number of a random subgraph of the Kneser graph
• Estimate of the number of edges in special subgraphs of a distance graph
• Clique numbers of random subgraphs of some distance graphs

This page was built for publication: Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs

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