MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Is there a characterization of graphs $G$ such that $\exists$ $\phi : G \rightarrow KG(n,k)$, where $KG(n,k)$ is the Kneser graph ($k \leq \lceil \frac{n}{2}\rceil $).

Any references on the subject will be appreciated.

share|cite|improve this question
up vote 8 down vote accepted

Homomorphisms into Kneser graphs are another way of describing fractional colourings; an introduction to how this all works is the topic of one of the chapters in my favourite book on Algebraic Graph Theory. There are other much more detailed references on fractional colourings, but not necessarily from the homomorphism viewpoint.

But just as there is no useful "characterization" of, say, graphs with 3-colourings (unless P=NP) there is no characterization of graphs with a given fractional chromatic number (except for a few trivial cases).

share|cite|improve this answer
I was hoping for some general strategy on how to prove a given graph is homomorphic to a given Kneser graph – hbm May 21 '12 at 20:54
I guess I have to rethink my question and reformulate again. Thanks. – hbm May 24 '12 at 10:23
@GordonRoyle Could you explain what is the exact connection between homomorphism to Kneser graphs and colorings? Can we tackle monomorphisms as well? – Turbo Oct 22 '13 at 7:47

From you original graph G, built a set system (on the same ground set as G) such that KG(F), the Kneser graph of F, is isomorphic to G.

I assume it is impossible if G contains a 1-cycle though.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.