Back to Search
Start Over
Maximal degrees in subgraphs of Kneser graphs
- Publication Year :
- 2020
-
Abstract
- In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph $KG(n,k)$. One of the main results asserts that, for $k>k_0$ and $n>64k^2$, whenever a non-empty subgraph has $m\ge k{n-2\choose k-2}$ vertices, its maximum degree is at least $\frac 12(1-\frac {k^2}n) m - {n-2\choose k-2}\ge 0.49 m$. This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree.
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2004.08718
- Document Type :
- Working Paper