SERENI , Jean-Sébastien

This thesis is comprised of three parts. In the first one,a channel assignment problem posed by Alcatel is modelledas a graph colouring problem: a graph is k-improperlyl-colourable if, given l colours,every vertex can be assigned a colour such that each colourclass induces a subgraph of maximum degree at most k.Several problems are studied:...

We introduce the process number of a digraph as a tool to study rerouting issues in \wdm networks. This parameter is closely related to the vertex separation (or pathwidth). We consider the recognition and the characterization of (di)graphs with small process number. In particular, we give a linear time algorithm to recognize (and process)...

The process number of a digraph has been introduced as a tool to study rerouting issues in WDM networks. We consider the recognition and the characterization of (di)graphs with process number at most two.

Improper choosability of planar graphs has been widely studied. In particular, Skrekovski investigated the smallest integer $g_k$ such that every planar graph of girth at least $g_k$ is $k$-improper $2$-choosable. He proved that $6\leq g_1\leq 9$; $5\leq g_2\leq 7$; $5\leq g_3\leq 6$ and $\forall k\geq 4, g_k=5$. In this paper, we study the...