41 citations · 71 across the 13 of their papers we have counts for
14 papers · 1 filter
Efficient computation of oriented vertex and arc colorings of special digraphs
Frank Gurski, Dominique Komander, Marvin Lindemann
In this paper we study the oriented vertex and arc coloring problem on edge series-parallel digraphs (esp-digraphs) which are related to the well known series-parallel graphs. Seri…
Acyclic coloring of special digraphs
Frank Gurski, Dominique Komander, Carolin Rehs
An acyclic r-coloring of a directed graph G=(V,E) is a partition of the vertex set V into r acyclic sets. The dichromatic number of a directed graph G is the smallest r such that G…
Oriented coloring on recursively defined digraphs
Frank Gurski, Dominique Komander, Carolin Rehs
Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring proble…
Comparing Linear Width Parameters for Directed Graphs
Frank Gurski, Carolin Rehs
In this paper we introduce the linear clique-width, linear NLC-width, neighbourhood-width, and linear rank-width for directed graphs. We compare these parameters with each other as…
Characterizations and Directed Path-Width of Sequence Digraphs
Frank Gurski, Carolin Rehs, Jochen Rethmann
Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an i…
Computing directed path-width and directed tree-width of recursively defined digraphs
Frank Gurski, Carolin Rehs
In this paper we consider the directed path-width and directed tree-width of recursively defined digraphs. As an important combinatorial tool, we show how the directed path-width a…