The chromatic number of $G$-stable Kneser graphs
Extending the notions of Kneser graphs and Schrijver graphs, we define the $G$-stable Kneser graph $KG(G,k)$ (where $k\geq 2$ and $G$ is a graph on $n\geq 2k$ vertices) as the graph whose vertices are the $k$-element independent sets in $G$ and whose edges join pairs of disjoint independent sets. The well-known result of Lovász on the chromatic number of Kneser graphs implies that $χ(KG(G,k)) \leq n-2k+2$ for any $G$. We call $G$ $k$-tight if equality holds, and we study the following question: Which graphs are $k$-tight? A result of Daneshpajouh et al.\ implies a characterization of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17884
curl -X POST /api/v1/records/arxiv/2610.17884/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17884/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'