# Homomorphism into Kneser graphs $KG(n, k)$

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.

-

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).

-
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.

-