Bounding the fractional chromatic number of K_Δ-free graphs

2012/06/11 by Edwards, Katherine, King, Andrew D.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1206.2384

Abstract

King, Lu, and Peng recently proved that for Δ≥ 4, any K_Δ-free graph with maximum degree Δ has fractional chromatic number at most Δ-\tfrac267 unless it is isomorphic to C₅\boxtimes K₂ or C₈². Using a different approach we give improved bounds for Δ≥ 6 and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's ω, Δ, χ conjecture.

Related

• The fractional chromatic number of K_Δ-free graphs
• The Fractional Chromatic Number of Triangle-free Graphs with Δ≤ 3
• The last fraction of a fractional conjecture
• Fractional chromatic number, maximum degree and girth
• Fractional total colourings of graphs of high girth