We provide a polynomial-time algorithm for b- Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by ...

While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ...

It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ...

The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural ...

We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ...

In this work, we solve three problems on well-partitioned chordal graphs. First, we show that every connected (resp., 2-connected) well-partitioned chordal graph has a vertex that intersects all longest paths (resp., longest ...

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...

Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, ...