The Rank-Width of Edge-Coloured Graphs |
| |
Authors: | Mamadou Moustapha Kanté Michael Rao |
| |
Affiliation: | 1. Clermont-Université, Université Blaise Pascal, LIMOS, CNRS, Complexe Scientifique des Cézeaux, 63173, Aubiére Cedex, France 2. Université Bordeaux 1, LaBRI, CNRS, 351 Cours de la libération, 33405, Talence Cedex, France
|
| |
Abstract: | A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${mathbb{F}}^{*}$ -graphs— $mathbb {F}$ -coloured graphs where each edge has exactly one colour from $mathbb{F}setminus {0}, mathbb{F}$ a field—and named respectively $mathbb{F}$ -rank-width and $mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $mathbb{F}^{*}$ -graphs and prove that $mathbb{F}^{*}$ -graphs of bounded $mathbb{F}$ -rank-width are characterised by a list of $mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $mathbb{F}$ is finite). An algorithm that decides in time O(n 3) whether an $mathbb{F}^{*}$ -graph with n vertices has $mathbb{F}$ -rank-width (resp. $mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $mathbb{F}^{*}$ -graphs of bounded $mathbb{F}$ -rank-width (resp. $mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|