CAM colloquium - Friday, March 4
3:30 p.m.
655 Rhodes Hall

Speaker: Maria Chudnovsky, Princeton/ CMI / IAS

 

Title: The Structure of Clawfree Graphs

Abstract: 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 describe some new properties of clawfree graphs, that we learned while working on the subject.

 

Refreshments at 4:30 in 657 Rhodes Hall.