**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.