Department of
Applied
Mathematics

Colouring claw-free graphs

Andrew King

McGill (& now Charles University)

Abstract

Chudnovsky and Seymour recently characterized the structure of claw-free graphs, generalizing previous work by Maffray and Reed on Berge claw-free graphs. When the stability number is at least four, a claw-free graph is a particular generalization of a line graph.

In this talk I will discuss the structure of claw-free graphs, and explain how we can use the structure theorems to extend two bounds on the chromatic number from line graphs to claw-free graphs. The first is Reed's conjecture on omega, Delta, and chi. The second states that the chromatic number is close to the fractional chromatic number. The proofs lead to polynomial-time algorithms for near-optimal colourings of claw-free graphs. This is joint work with Bruce Reed.