Title: Parties, doughnuts and coloring
Abstract: This is a gentle introduction to graph theory, connecting familiar concepts and classical problems with most recent cutting edge research in the field.
Title: Coloring Graphs with Forbidden Induced Subgraphs
Abstract: The problem of testing if a graph can be colored with a given number k of colors is NP-complete for every k>2. But what if we have more information about the input graph, namely that some fixed graph H is not present in it as an induced sub-graph? It is known that the problem remains NP-complete even for k=3, unless H is the disjoint union of paths. We consider the following two questions:
1. For which graphs H is there a polynomial time algorithm to 3-color (or in general k-color) an H-free graph?
2. For which graphs H are there finitely many 4-critical H-free graphs?
This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.
Title: Perfect and Beyond
Abstract: About 10 years ago one of the central open problems in graph theory at the time, the Strong Perfect Graph Conjecture, was solved. The proof used structural graph theory methods, and spanned 155 journal pages. The speaker was part of the team of authors of this mathematical beast. In this talk we will explain the problem, describe some of the ideas of the proof (that has since been shortened somewhat), and discuss related problems that have been a subject of more recent research.
The lectures are supported by the Arne Magnus Lecture Fund and the Albert C. Yates Endowment in Mathematics.
Contributions to the Magnus Fund are greatly appreciated and may be made through the Department of Mathematics. Please contact Sheri Hofeling (firstname.lastname@example.org) at at (970)-491-7047 for specific information.
All lectures are free and open to the public.