Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, November 23, 2004 - 4:30pm

Maria Chudnovsky

Princeton/CMI/IAS

Location

University of Pennsylvania

DRL 4N30

A graph is said to be clawfree if it has no induced subgraph isomorphic to $K_{1,3}$. Line graphs are one well-known class of clawfree graphs, but there others, such as circular arc graphs and subgraphs of the Schl\"{a}fli graph. It has been an open question to describe the structure of all clawfree graphs. Recently, in joint work with Paul Seymour, we were able to prove that all clawfree graphs can be constructed from basic pieces (which include the graphs mentioned above, as well as a few other ones) by gluing them together in prescribed ways. In this talk we will survey some ideas of the proof, and present examples of clawfree graphs that turned out to be of importance in the description of the general structure. We will also some describe new properties of clawfree graphs, that we learned while working on the subject.