Graph colorings and applications

Description

This thesis is comprised of three parts. In the first one,
a channel assignment problem posed by Alcatel is modelled
as a graph colouring problem: a graph is k-improperly
l-colourable if, given l colours,
every vertex can be assigned a colour such that each colour
class induces a subgraph of maximum degree at most k.
Several problems are studied: improper colouring (and improper choosability) of graphs with bounded density (including the case of graphs of given genus and girth), unit disk graphs (including random instances and inifinite set of points), and also weighted improper colouring of subgraphs of the triangular lattice.

In the second part, different kinds of colouring, for
which we obtain new results, are studied: 3-facial colourings of plane graphs, circular choosability, and various types of edge-colourings of cubic graphs, in particular by elements of Abelian groups, and Steiner triple systems.

In the last part, we focus on a rerouting problem, without
service interruption, in WDM networks. First, a new invariant is introduced so as to model this problem. As it turns out that this parameter is close to the pathwidth, we then present some new results we get concerning the relation between the pathwidth of a 2-connected outerplanar graph and the pathwidth of its dual.

Abstract (French)

Cette thèse comporte trois parties. Dans la première partie, un problème d'allocation de fréquences, proposé par Alcatel, est modélisé en termes de coloration de graphes : un graphe est k-improprement l-colorable
s'il est possible, étant données l couleurs, d'attribuer une couleur à chacun de ses sommets de sorte que chaque sommet ait au plus k voisins de la même couleur que lui.
Différentes problématiques sont ensuite étudiées :
la coloration impropre (et la choisissabilité impropre) des
graphes de densité bornée (englobant le cas des graphes de genre borné et de maille donnée), celles des graphes d'intersection de disques unitaires (y compris
pour des instances aléatoires, et pour des ensembles de points infinis), ainsi que la coloration impropre pondérée des sous-graphes du réseau triangulaire.

La deuxième partie regroupe différents problèmes de colorations de graphes, plus ou moins reliés au problème d'allocation de fréquences, pour lesquels nous avons obtenus de nouveaux résultats. Il s'agit de la coloration 3-faciale des graphes planaires, de la choisissabilité circulaire et de diverses généralisations de l'arête-coloration des graphes cubiques, en particulier par des éléments de groupes abéliens, et des triplets de Steiner.

Dans la troisième partie, nous nous intéressons à un problème de reroutage de requêtes, sans perte de service, dans les réseaux WDM. Dans un premier temps, un nouvel invariant des graphes est introduit afin de modéliser cette question.
Comme il s'avère que ce paramètre est proche de celui, bien connu, de largeur arborescente linéaire (pathwidth), ce dernier nous a également intéressé et nous avons
obtenu de nouveaux résultats concernant la relation entre la largeur arborescente lineaire d'un graphe planaire extérieur 2-connexe et celle de son dual.

Additional details