10
$\begingroup$

Kneser graphs $KG(n, k)$ are well known: the vertices are all $k$-subsets of $\{1,2,\dotsc,n\}$ with two sets connected iff they are disjoint. If the graph is odd (i.e., has an odd number of vertices) it is easy to see (by regularity) that the edge chromatic number is $d+1$ where $d$ is the maximum degree (i.e., graph is Class Two). What if the graph is even? I have done computations up to $n = 14$ and it appears that all the even graphs are Class One with the sole exception of the Petersen Graph -- $KG(5,2)$ -- which is Class Two.

Is this known? If not, feel free to prove it!

0 Answers 0