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.)
|
4 | deleted 1 characters in body | ||
|
|
||||
|
|
3 | make mathjax happier | ||
|
Bondy and Hell, in their paper on the star chromatic number, prove that
|
||||
|
|
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 |
|
||
