The Summer Undergraduate Research Fellowship (SURF) program allows students to research under the guidance of professors.
I worked with professor Richard M. Wilson the summer of 2006 and 2007.
A theorem of Erdős implies that we can make χ(G) arbitrarily large while fixing ω(G) = 2. Therefore in general we cannot bound χ(G) above by a function of ω(G). In 2005, Chudnovsky and Seymour showed that if G is 3-claw-free with α(G) > 3, then χ(G) < 2ω(G). We attempt to improve upon this result for subclasses of 3-claw-free graphs and also generalize this result to k-claw-free graphs.
A 4-hole is four vertices joined together in a square, but neither of the diagonals is joined. We show that if G is k-claw-free, and 4-hole-free, with α(G) > k, then χ(G) < k (k – 1) ω(G) / 2 – 1.