Johnson graphs have a dual like construction to Kneser graphs in the sense that in Kneser we encode non-intersecting k-sets by joining vertices that represent the sets while in Johnson graphs we encode intersecting k-1-sets.

I have a few questions on Johnson graphs:

What is the fractional chromatic number $\chi_f(J(n,2))$ of Johnson graph $J(n,2)$ which is the complement of Kneser graph $K(n,2)$?

In general what is $\chi_f(J(n,k))$?

It is known that we have a graph homomorphism $G\rightarrow K(n,m)$ if and only if $\chi_f(G)=\frac{m}{n}$ for any graph $G$. Is there a similar relation for Johnson graphs(atleast for $J(n,2)$)?

In general do we have $G\leftrightarrow H\iff\chi_f(G)=\chi_f(H)$? (where $\leftrightarrow$ implies homomorphisms bothways?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.