***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday September 19th, 4:30 in Fine Hall 224.
 
Speaker: Maria Chudnovsky, Columbia

Title: Three-coloring graphs with no induced 6-edge paths

Since graph-coloring is an NP-complete problem in general, it is 
natural to ask how the complexity changes if the input graph is known not 
to contain a certain induced subgraph H. Results of Kaminski and Lozin, 
and Hoyler, show that the problem remains NP-complete unless H is a 
disjoint union of paths. Recently the complexity of coloring graphs with a 
fixed-length induced path forbidden has received considerable attention, 
and only a few cases of that problem remain open for k-coloring when k>=4. 
However, little is known for 3-coloring. Recently we have settled the 
first open case for 3-coloring; namely we showed that deciding 3-colorability
for graphs with no induced 6-edge paths can be done in polynomial time. 
In this talk we will discuss some of the ideas of the algorithm.

This is joint work with Peter Maceli and Mingxian Zhong.


                       -----------

Next week: Eli Berger

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)