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

DOI10.1134/S1064562414050147zbMath1306.05222MaRDI QIDQ483670

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

Publication date: 17 December 2014

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

independence numberchromatic numberrandom graph

Mathematics Subject Classification ID

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

Related Items (21)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• Excursions into combinatorial geometry
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring Distance Graphs and Graphs of Diameters
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Research Problems in Discrete Geometry
• The chromatic number of random graphs
• The chromatic number of random graphs

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