Computer Science – Discrete Mathematics
Scientific paper
2010-09-30
Computer Science
Discrete Mathematics
7 pages, 0 figures. Version 2: extended introduction, fixed some notation, and clarified equations on p. 6
Scientific paper
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 associations
LandOfFree
A stronger result on fractional strong colourings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A stronger result on fractional strong colourings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A stronger result on fractional strong colourings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-327088