The chromatic number of G-stable Kneser graphs

Abstract

Extending the notions of Kneser graphs and Schrijver graphs, we define the G-stable Kneser graph KG(G,k) (where k≥ 2 and G is a graph on n≥ 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)) ≤ 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 $2$-tight graphs. We prove a necessary condition for a graph to be k-tight for k≥ 3 which extends this characterization, and we conjecture it to be sufficient. Another result gives a lower bound to the chromatic number of the G-stable Kneser graphs when G is a disjoint union of cycles. We use this result to give a short proof of the fact that $4$-regular graphs on 3k vertices consisting of two vertex-disjoint cycles and k cycles of length $3$ admit an independent set of size k.

On the k-Distance Chromatic Number of Unicyclic Graphs
Rosário Fernandes, Rúben Palma
Discrete Mathematics Letters25 Oct 2026Peer-reviewedCC BYFull textGeneral mathematicsDOAJ
Minimal Cayley graphs with large chromatic number
James Davies, Meike Hatzel, Liana Yepremyan
arXiv13 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Geometric triangle-free graphs of large chromatic number
István Tomon
arXiv6 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
Box-Delaunay graphs of large chromatic number
István Tomon
arXiv1 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
Lasitha Jayasinghe
arXiv6 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{arana2026chromatic,
  title = {{The chromatic number of $G$-stable Kneser graphs}},
  author = {Carmen Arana and Penny Haxell and Tomáš Kaiser and Matěj Stehlík},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17884},
  eprint = {2610.17884},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17884},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - The chromatic number of G-stable Kneser graphs
AU  - Carmen Arana
AU  - Penny Haxell
AU  - Tomáš Kaiser
AU  - Matěj Stehlík
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17884
UR  - https://arxiv.org/abs/2610.17884
AB  - Extending the notions of Kneser graphs and Schrijver graphs, we define the G-stable Kneser graph KG(G,k) (where k≥ 2 and G is a graph on n≥ 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)) ≤ 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 $2$-tight graphs. We prove a necessary condition for a graph to be k-tight for k≥ 3 which extends this characterization, and we conjecture it to be sufficient. Another result gives a lower bound to the chromatic number of the G-stable Kneser graphs when G is a disjoint union of cycles. We use this result to give a short proof of the fact that $4$-regular graphs on 3k vertices consisting of two vertex-disjoint cycles and k cycles of length $3$ admit an independent set of size k.
ER  -

Abstract

Related

Cite