August 6, Wednesday
12:00 – 13:30
Induced Cycles and Chromatic Number - a result by A. D. Scott
Graduate seminar
Lecturer : Mr. Elad Horev
Lecturer homepage : http://www.cs.bgu.ac.il/faculty/person/horevel.html
Affiliation : CS, BGU
Location : 202/37
Host : Grduate seminar
For any integer k, there exists an integer g(k) such that every graph with chi(G) geq g(k) contains either a K_k or an odd hole of length at least 5.
In 1996, in a rather short and elegant proof, Scott provided a partial answer to the above conjecture. In addition, the result of Scott also provides a partial answer to another conjecture put forth by Sumner in 1981. Recently, Chudnovsky, Robertson, Seymour, and Thomas have obtained additional advancement regarding the conjecture of Gyarfas.
A discussion as to the result of Scott is offered.