Computer Science – Discrete Mathematics
Scientific paper
2007-09-10
Computer Science
Discrete Mathematics
It is an update of the last version generalising all the results to edge-colored graphs and answering some of the raised quest
Scientific paper
Clique-width is a complexity measure of directed as well as undirected graphs. 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 an extension of the notion of rank-width to edge-colored graphs. A C-colored graph is a graph where the arcs are colored with colors from the set C. There is not a natural notion of rank-width for C-colored graphs. We define two notions of rank-width for them, both based on a coding of C-colored graphs by edge-colored graphs where each edge has exactly one color from a field F and named respectively F-rank-width and F-bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for F-colored graphs and prove that F-colored graphs of bounded F-rank-width are characterised by a finite list of F-colored graphs to exclude as vertex-minors. A cubic-time algorithm to decide whether a F-colored graph has F-rank-width (resp. F-bi-rank-width) at most k, for fixed k, is also given. Graph operations to check MSOL-definable properties on F-colored graphs of bounded rank-width are presented. A specialisation of all these notions to (directed) graphs without edge colors is presented, which shows that our results generalise the ones in undirected graphs.
Kante Mamadou Moustapha
Rao Michaël
No associations
LandOfFree
The Rank-Width of Edge-Colored Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Rank-Width of Edge-Colored Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Rank-Width of Edge-Colored Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-656438