Claw-decomposition of Kneser Graphs

Abstract

A claw is a star with three edges‎. ‎The Kneser graph $KG_{n,2}$ is the graph whose vertices are the ‎$‎2‎$‎-subsets of an $n$-set‎, ‎in which two vertices are adjacent if and only if their intersection is empty‎. ‎In this paper‎, ‎we prove that $KG_{n,2}$ is claw-decomposable‎, ‎for all $n \geq 6$‎.

Keywords

• ‎decomposition‎
• ‎tensor product‎
• ‎kneser graph‎
• ‎crown graph‎
• ‎star