Title: Bounding the Fractional Chromatic Number of K_Delta -free Graphs
Speaker: Katherine Edwards, Princeton University
Date: Tuesday, April 22, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Fractional colouring is a generalization of graph colouring in which vertices are assigned sets of colours so that every pair of adjacent vertices receive disjoint sets. The fractional chromatic number is bounded above by the maximum degree Delta, but in graphs which do not contain a clique of size Delta we can generally find stronger upper bounds. I will discuss some recent progress in bounding the fractional chromatic number of K_Delta -free graphs away from Delta. Our method relies on a local strengthening of the fractional relaxation of Reed's omega, Delta, chi conjecture which roughly stipulates that if a graph has high fractional chromatic number then it must contain a vertex of high degree and a large clique in the same local area of the graph. I will also discuss new, stronger local bounds on the fractional chromatic number. Joint work with Andrew King.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math