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?
The fractional chromatic number as a lower bound for the chromatic number for graph coloring
2
$\begingroup$
graph-theory
coloring
1 Answers
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). $