1
$\begingroup$

A fractional coloring of $G(V,E)$ is a function $f:{2^{|V|}} \to [0,1]$ such that $f(S) > 0$ only if $S$ is an independent set in $G$, and for all $v \in V$, it holds $\sum\nolimits_{S:v \in S} {f(S) \ge 1} $. A fractional chromatic number $\chi_f(G)$ is the minimum $k$ for which there exists a fractional coloring $f$ for $G$ with $\sum\nolimits_S {f(S) = k} $.

Let $G = (V,E) $ be a graph and let $k \in \mathbb{N}$. Show that ${\chi_f}(G) \le k$ if and only if for all weight function $w:V \to \mathbb{R}_+$ there is an independent set of size at least $\left( {\sum\nolimits_{v \in V} {w(v)} } \right)/k$. Moreover, if we are given an algorithm that computes an independent set of size $w(V)/k$ for all weight function $w$, then this algorithm can be used to compute a fractional coloring using $(1 + \varepsilon )k$ colors.

Where i can read about the proof of this claim?

$\endgroup$
3
  • $\begingroup$ Hi, welcome to MO. What is $\epsilon$? What is $X_f (G)$? I think that more details can help.... $\endgroup$
    – Amir Sagiv
    Commented Apr 7, 2017 at 10:14
  • $\begingroup$ @AmirSagiv $\varepsilon \in (0,0.5)$ and ${\chi_f}$ - fractional chromatic number $\endgroup$
    – user_777
    Commented Apr 7, 2017 at 10:18
  • $\begingroup$ You should add these details, with their definitions, in the original post. $\endgroup$
    – Amir Sagiv
    Commented Apr 7, 2017 at 10:19

1 Answer 1

2
$\begingroup$

A Note on Fractional Coloring and the Integrality gap of LP for Maximum Weight Independent Set, Parinya Chalermsook and Daniel Vaz (2016).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .