McGill University - School of Computer Science

Algorithms Seminar 2005

Everybody is welcome!

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.

mailing list info: