Graph colouring and applications

Habilitation à diriger des recherches

Frédéric Havet

 
My "habilitation" will be defended on December 12 2007 at 10h at INRIA Sophia-Antipolis. This "habilitation" is made of an introduction to graph colouring and the work I did in this area over the past few years, and the papers corresponding to this work. All the material of the "habilitation" is now posted here.

Introduction

Intro.pdf

Colouring with constraints at distance two or more

L(2,1)-labellling of graphs, with B. Reed and J.-S. Sereni     .pdf.

List colouring squares of planar graphs, with J. van den Heuvel, C. McDiarmid and B. Reed.
Extended abstract to appear in Eurocomb'07, September 2007, Seville.    .pdf.
Full version     .pdf.

Choosability of the square of planar graphs with large girth
Discrete Mathematics, to appear.     .pdf.

3-facial colouring of plane graphs, with J.-S. Sereni and R. Skrekovski
SIAM J. of Discrete Math., to appear.     .pdf.

(p,1)-total labelling of graphs, with M.L. Yu.
Discrete Mathematics, to appear.    .pdf.

Complexity of (p, 1)-total labelling, with S. Thomassé
Submitted.     .pdf.

Improper colouring

Improper choosability of graphs and maximum average degree, with J.-S. Sereni.
Journal of Graph Theory, 52 (3), 181-199 (2006).     .pdf.

Channel assignment and multicolouring of the induced subgraphs of the triangular lattice.
Discrete Mathematics  233 (1-3), 219-231 (2001).    .pdf.

Finding a five bicolouring of a triangle-free subgraph of the triangular lattice, with J. Zerovnik.
Discrete Mathematics,  244, 103-108 (2002).    .pdf.

Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés, with J.-C. Bermond, F. Havet, F. Huc and C. Linhares-Sales
Preliminary version in french: In 9emes rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'2007), Ile d'Oleron, France, Mai 2007.     .pdf.

Improper colouring of unit disk graphs, with R. Kang and J.-S. Sereni
Submitted,    .pdf.

Colouring the arcs of a digraph

Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree, with S. Bessy, E. Birmelé
Journal of Graph Theory, 53 (4), 315-332 (2006).   .pdf.

WDM and directed star arboricity, with O. Amini, F. Huc and S. Thomassé
Submitted.     .pdf.