Consider the following two ways to colour the vertices of a graph where the requirement that
adjacent vertices get distinct colours is relaxed. A colouring has" defect" $ d $ if each …

We investigate the parameterized complexity of Bayesian Network Structure Learning
(BNSL), a classical problem that has received significant attention in empirical but also …

We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem
(BDD), where the aim is to find a maximum induced subgraph whose maximum degree is …

We show that some natural problems that are XNLP-hard (hence-hard for all t) when
parameterized by pathwidth or treewidth, become FPT when parameterized by stable …

Hadwiger's conjecture asserts that every K t‐minor‐free graph has a proper (t− 1)‐colouring.
We relax the conclusion in Hadwiger's conjecture via improper colourings. We prove that …

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue
of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it …

Several min–max relations in graph theory can be expressed in the framework of the Erdős–
Pósa property. Typically, this property reveals a connection between packing and covering …

We introduce a graph-parametric framework for obtaining obstruction characterizations of
graph parameters with respect to partial ordering relations. For this, we define the notions of …

We study the parameterized complexity of computing the tree-partition-width, a graph
parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand …

The decomposition of graphs is a prominent algorithmic task with numerous applications in
computer science. A graph decomposition method is typically associated with a width …