On random subgraphs of Kneser and Schrijver graphs

DOI10.1016/J.JCTA.2016.02.003zbMath1334.05158arXiv1502.00699OpenAlexW2963509447MaRDI QIDQ272313

Andrey B. Kupavskii

Publication date: 20 April 2016

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.00699

zbMATH Keywords

chromatic numberKneser graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (18)

On a bound in extremal combinatorics ⋮ Choice number of Kneser graphs ⋮ Sharp bounds for the chromatic number of random Kneser graphs ⋮ Chromatic number of random Kneser hypergraphs ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Independence numbers of random subgraphs of some distance graph ⋮ A generalization of Kneser graphs ⋮ 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 chromatic number of a random subgraph of the Kneser graph ⋮ Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\) ⋮ On the Hadwiger number of Kneser graphs and their random subgraphs ⋮ On threshold probability for the stability of independent sets in distance graphs ⋮ Large cycles in random generalized Johnson graphs ⋮ Clique numbers of random subgraphs of some distance graphs ⋮ On the chromatic number of random subgraphs of a certain distance graph ⋮ 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
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• Kneser's conjecture, chromatic number, and homotopy
• On the stability of the Erdős-Ko-Rado theorem
• A short proof of Kneser's conjecture
• TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• The Chromatic Number of Kneser Hypergraphs
• A New Short Proof of Kneser's Conjecture
• Extremal Results in Random Graphs
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: On random subgraphs of Kneser and Schrijver graphs