Time: 12:00 noon Tuesday, 8th November 2016.
Location: SIT 459
Speaker: Shenwei Huang, UNSW
Title: Colouring on hereditary graph classes
A graph class is hereditary if it is closed under taking induced subgraphs. It is known that hereditary classes can be characterized by forbidden induced subgraphs. We survey some recent complexity results on colouring on hereditary classes, mainly focusing on graphs that do not contain a path on t vertices for any fixed t. If time permitted, we will also talk about a result on colouring even-hole-free graphs, i.e., graphs that do not contain any cycle of even length as an induced subgraph.