moteur de recherche

Séminaire Algo - Nicolas Trotignon
Séminaire Algo - Nicolas Trotignon
28-nov.-2017 14:30
Il y a: 1 year

Nicolas Trotignon

Graphs classes defined by excluding Truemper Configurations

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: Truemper configurations are simple structures : prisms, thetas, pyramids and wheel. A prism is a graph made of two disjoint triangle that are matched by three disjoint paths. A theta is a graph made of two disjoint vertices that are linked by three disjoint paths. A pyramid is a graph made of a vertex and triangle that are linked by three disjoint paths. A wheel is a chordless cycle together with a vertex disjoint from it, and with at least three neighbors in it. In this abstract we omitted technical requirements on the lengths of the paths and cycles.

Truemper configuration play an important in role in several theorems. For instance, they appear in an old characterisation of graph with no cycle through three prescribed vertices (due to Watkins and Mesner). They appear in a theorem of Truemper about signing edges of a graph in such way that several constraints on the parity of cycles are satisfied. And they play an important role in many recent decomposition theorems in structural graph theory (perfect graphs, even-hole-free graphs, claw-free graphs, bull-free graphs, and some others).

The talk will focus on this last aspect. I will explain why Truemper Configuration are important in decomposition theorems. Then I will present a project about systematically studying the classes of graph where Truemper configuration are excluded.

Joint work with Marko Radovanovic and Kristina Vuskovic.

<- retour: