4 deleted 1 characters in body

Bondy and Hell, in their paper on the star chromatic number, prove that $$\chi_f(G) = \min \left\{ \frac{n}{k}: G\to KG(n,k) \right\}$$ Note that we have $\min$ here, not $\inf$. So the answer to your first question is yes. The proof of this result in my favorite book on Algebraic Graph Theory (which I am pretty sure follows that of Bandy and Hell) constructs the required homomorphism from the fractional coloring. Hence I suspect that the answer to your second question is that it is hard to determine the minimum value of $n$ needed. (But I do not know, and I do not recall seeing anything on this point.)

3 make mathjax happier

Bondy and Hell, in their paper on the star chromatic number, prove that $$\chi_f(G) = \min \left\{ \frac{n}{k}: G\to KG(n,k) \right\}$$Note that we have $\min$ here, not $\inf$. So the answer to your first question is yes. The proof of this result in my favorite book on Algebraic Graph Theory (which I am pretty sure follows that of Bandy and Hell) constructs the required homomorphism from the fractional coloring. Hence I suspect that the answer to your second question is that it is hard to determine the minimum value of $n$ needed. (But I do not know, and I do not recall seeing anything on this points.)

2 added 484 characters in body

Bondy and Hell, in their paper on the star chromatic number, prove that $$\chi_f(G) = \min \left{ left\{ \frac{n}{k}: G\to KG(n,k) \right} right\}$$ Note that we have $\min$ here, not $\inf$. So the answer to your first question is yes. The proof of this result in my favorite book on Algebraic Graph Theory (which I am pretty sure follows that of Bandy and Hell) constructs the required homomorphism from the fractional coloring. Hence I suspect that the answer to your second question is that it is hard to determine the minimum value of $n$ needed. (But I do not know, and I do not recall seeing anything on this points.)

Post Undeleted by Chris Godsil
Post Deleted by Chris Godsil
1