On the chromatic number of a random subgraph of the Kneser graph

DOI10.1134/S1064562417050209zbMath1378.05062OpenAlexW2765494462MaRDI QIDQ679977

S. G. Kiselev, Andrei M. Raigorodskii

Publication date: 22 January 2018

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

Full work available at URL: https://doi.org/10.1134/s1064562417050209

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Sharp bounds for the chromatic number of random Kneser graphs ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Estimate of the number of edges in special subgraphs of a distance graph ⋮ A generalization of Kneser graphs ⋮ On the random version of the Erdős matching conjecture ⋮ On threshold probability for the stability of independent sets in distance graphs ⋮ The number of edges in induced subgraphs of some distance graphs ⋮ On the chromatic number of random subgraphs of a certain distance graph ⋮ Degree versions of theorems on intersecting families via stability ⋮ Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)

Cites Work

• Unnamed Item
• On random subgraphs of Kneser and Schrijver graphs
• Lovász' theorem on the chromatic number of spheres revisited
• Independence numbers of random subgraphs of a distance graph
• On the number of edges in induced subgraphs of a special distance graph
• On chromatic numbers of nearly Kneser distance graphs
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• On the stability of some Erdős-Ko-Rado type results
• On random subgraphs of Kneser graphs and their generalizations
• On the stability of the Erdős-Ko-Rado theorem
• New upper bound for the chromatic number of a random subgraph of a distance graph
• On the chromatic numbers of low-dimensional spaces
• Colorings of partial Steiner systems and their applications
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Combinatorial Geometry and Coding Theory*

This page was built for publication: On the chromatic number of a random subgraph of the Kneser graph