Some problems in graph theory and graphs algorithmic theory
Habilitation à diriger des recherches
Here is posted all the material for my "habilitation à diriger des recherches".
The whole document is available here.
Introduction
Here is an introduction to my research work presented in my
Habilitation: Introduction.
Part I: problems on
cycles in digraphs
- S. Bessy, S. Thomassé, Spanning a
strong digraph with alpha cycles: a conjecture of
Gallai. Combinatorica,
27 (6), 2007, 659--667.
- S. Bessy, N. Lichiardopol and J.-S. Sereni,
Two proofs of Bermond-Thomassen
conjecture for regular tournaments.
Discrete
Mathematics, 310 (3), 2010,
557--560.
- J. Bang-Jensen, S. Bessy and S. Thomassé,
Disjoint 3-cycles in tournaments: a proof of the
Bermond-Thomassen conjecture for tournaments,
submitted.
Part II: colouring and
partitionnig problems
- S. Bessy, S. Thomassé,
Partitionning a graph into a cycle and an
anticycle, a proof of Lehel's conjecture.
Journal of Combinatorial Theory Serie B,
100 (2), 2010, 176--180.
- S. Bessy, E. Birmelé, F. Havet,
Arc-chromatic number of digraphs
in which every vertex has bounded outdegree or bounded indegree.
Journal of Graph
Theory, 53 (4), 2006,
315--332.
- S. B., C. Lepelletier,
Optical index of fault tolerant routings in
WDM networks. Networks,
56 (2), 2010,
95--102.
Part III: algorithmic problems
on graphs
- S. Bessy, C. Paul and A. Perez,
Polynomial kernels for 3-leaf power graph
modification problems. IWOCA 2009:72--82,
et
Discrete Applied Mathematics, 158
(2010) pp. 1732-1744 .
- S. Bessy, F.V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh and
S.Thomassé,
Kernels for Feedback Arc Set In Tournaments.
FSTTCS 2009: 37-47, et accepté
à Journal of Computer and System Sciences.
- S. Bessy and A. Perez,
Polynomial kernels for Proper Interval Completion and
related problems. accepted in FCT 2011
- S. Bessy and F. Havet
Enumerating the edge-colourings and total colourings of a regular
graph. accepted in Journal of
Combinatorial Optimization.