9 citations · 10 across the 2 of their papers we have counts for
6 papers · 1 filter
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…
Counting and Enumerating Independent Sets with Applications to Knapsack Problems
Frank Gurski, Carolin Rehs
We introduce methods to count and enumerate all maximal independent, all maximum independent sets, and all independent sets in threshold graphs and k-threshold graphs. Within thres…