Colorations de graphes et applications
Jean‐Sébastien Sereni · HAL (Le Centre pour la Communication Scientifique Directe) · 2006
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.