2
$\begingroup$

I need to show or prove that the fractional chromatic number is a lower bound for the chromatic number k for graph coloring. Any idea on how I can prove this?

1 Answers 1

1

A $b$-fold coloring is a coloring in which every vertex is assigned a set of $b$ colors. The $b$-fold chromatic number $\chi_b(G)$ is the least number such that a $b$-fold coloring exists. Notice that $\chi_1(G) = \chi(G)$, the usual chromatic number. We have $ \chi_f(G) = \inf_{b \rightarrow \infty} \frac{\chi_b(G)}{b} \leq \frac{\chi_1(G)}{1} = \chi(G). $