you're reading...

SACT Seminar: Colouring on hereditary graph classes

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.


No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 75 other followers

%d bloggers like this: