DATE: | Wednesday, January 12th 2004. |
TIME: | 4:30 PM - 5:30 PM |
PLACE: | McConnell 320 |
TITLE: | The Structure of Clawfree Graphs |
SPEAKER: | Maria Chudnovsky, Princeton/CMI/IAS |
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 are others, such as circular arc
graphs, the icosahedron and the Schl\"{a}fli graph, and it has been an open question to describe
the structure of all clawfree graphs. Recently 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
others) by gluing them together in prescribed ways. This talk 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.