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.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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).
answered May 21, 2012 at 13:04
-
$\begingroup$ I was hoping for some general strategy on how to prove a given graph is homomorphic to a given Kneser graph $\endgroup$– hbmCommented May 21, 2012 at 20:54
-
$\begingroup$ I guess I have to rethink my question and reformulate again. Thanks. $\endgroup$– hbmCommented May 24, 2012 at 10:23
-
$\begingroup$ @GordonRoyle Could you explain what is the exact connection between homomorphism to Kneser graphs and colorings? Can we tackle monomorphisms as well? $\endgroup$– TurboCommented Oct 22, 2013 at 7:47
$\begingroup$
$\endgroup$
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.
