October 23-24, 2017

Departments of Mathematics

PACM: The Program in Applied and Computational Mathematics

Princeton University

Monday, October 23, 2017

4:00-5:00pm

Location: 221 TiLT Building

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

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.

4:00 - 5:00 p.m.

Location:

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 (hofeling@math.colostate.edu) at at (970)-491-7047 for specific information.

All lectures are free and open to the public.