2010/09/30 by Andrew D. King, King, Andrew D.
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1010.0032
Withdrawn -- critical error in the proof of the main lemma
openalex publication_date 2010/09/30 · arxiv created 2014/10/09 · arxiv updated 2014/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥ 1 and partition the vertices of a graph G into sets V1,..., Vr, such that for 1≤ i ≤ r every vertex in Vi has at most max\k, |Vi|-k \ neighbours outside Vi. 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 Vi with probability 1/|Vi|, for 1≤ i≤ r. We believe that this result will be useful as a tool in probabilistic approaches to bounding the chromatic number and fractional chromatic number.