Take the 2-minute tour ×
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.

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|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.