The Arne Magnus Lectures
October 23-24, 2017

M. Gregory Forest


MacArthur Fellow, 2012
Departments of Mathematics
PACM: The Program in Applied and Computational Mathematics
Princeton University

Monday, October 23, 2017
Location: 221 TiLT Building
Reception following lecture
Weber 117
5:00 - 6:00 pm

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.

Tuesday, October 24, 2017
11:00 am-12:00 pm
Location: Weber 223
Department reception prior to talk
Weber 117
10:30 - 11:00 am

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.

Tuesday, October 24, 2017
4:00 - 5:00 p.m.

Location: Weber 223
Department reception prior to talk
Weber 117
3:30 -4:00 pm

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 Arne Magnus Lectures are given annually in the Department of Mathematics at Colorado State University in honor of Dr. Arne Magnus, our friend and colleague for 25 years.

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 ( at at (970)-491-7047 for specific information.

All lectures are free and open to the public.