Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Kneser graphs KG(n, k) are well known: vertices are all k-subsets of {1,2,...,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!

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.