Polynesian Journal of Mathematics

Volume 3, Issue 2

A note on the chromatic number of Kneser graphs on chambers of projective planes and incidence-free sets

Philipp Heering, Klaus Metsch, Vladislav Taranchuk, and Zsuzsa Weiner

Abstract:

Let $D=(𝒫,B)$ be a symmetric $(v,k,\lambda )$-design and let $(X,Y)$ be an equinumerous incidence-free pair, with $X\subseteq 𝒫$ and $Y\subseteq B$. In this note, we give an elementary proof which shows the existence of a perfect matching between $𝒫\setminus X$ and $B\setminus Y$ in the incidence graph of $D$. This recovers a result of Spiro, Adriaensen, and Mattheus, who already showed this using different arguments for $k\ge 36$. We use this to connect some dots in the literature and prove that finding the chromatic number of the Kneser graph on chambers of a projective plane is equivalent to finding the incidence-free number of the incidence graph of the plane. Furthermore, we construct an incidence-free pair for PG$(2,q^2)$ of size roughly $q^3∕2+3q^2∕4$.

Citation:

Philipp Heering, Klaus Metsch, Vladislav Taranchuk, and Zsuzsa Weiner. A note on the chromatic number of Kneser graphs on chambers of projective planes and incidence-free sets. Polynesian Journal of Mathematics, Volume 3, Issue 2, Pages 1–8. (Aug. 2026) DOI: 10.69763/polyjmath.3.2

Export to BibTeX

Milestones:

Received 13 May 2026
Revised 14 Jul 2026
Accepted 26 Jul 2026
Published 12 Aug 2026
Communicated by Roger Oyono

The above content is published under the terms of the Creative Commons Attribution 4.0 International license.