A stronger result on fractional strong colourings

Aharoni, Berger and Ziv recently proved the fractional relaxation of the strong colouring conjecture. In this note we generalize their result as follows. Let $k\geq 1$ and partition the vertices of a graph $G$ into sets $V_1,..., V_r$, such that for $1\leq i \leq r$ every vertex in $V_i$ has at most $\max\{k, |V_i|-k \}$ neighbours outside $V_i$. Then there is a probability distribution on the stable sets of $G$ such that a stable set drawn from this distribution hits each vertex in $V_i$ with probability $1/|V_i|$, for $1\leq i\leq r$. We believe that this result will be useful as a tool in probabilistic approaches to bounding the chromatic number and fractional chromatic number.

No reviews yet.

No comments yet.