The Rank-Width of Edge-Coloured Graphs

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 ³) 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.