2
$\begingroup$

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

$\endgroup$

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.