thesis

Excluding slightly more than a cycle

Defense date:

Jan. 1, 2013

Edit

Institution:

Paris 7

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

This thesis is concerned with structural graph theory. It contains several results, algorithmics and structural, on classes of graphs defined by forbidding induced subgraphs. Graphs that are excluded are variations around the so-called "Truemper configurations". These last might be seen as generalization of the cycle.

Abstract FR:

Cette thèse concerne la théorie structurelle des graphes. Elle contient un certain nombre de résultats, aussi bien algorithmiques que structurels, sur les graphes ne contenant pas certains graphes en tant que sous graphes ou sous-graphes induits. Les graphes exclus consistent en des variations autour des configurations de Truemper. Celles-ci peuvent être vues comme des généalisations du cycle.