38 citations · 246 across the 68 of their papers we have counts for
18 papers · 1 filter
Bounding Width on Graph Classes of Constant Diameter
Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Köhler +2
We determine if the width of a graph class changes from unbounded to bounded if we consider only those graphs from whose diameter is bounded. As parameters we…
The complexity of L(p,q)-Edge-Labelling
Gaetan Berthe, Barnaby Martin, Daniel Paulusma +1
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially class…
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injec…
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná +2
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph…
On the Parameterized Complexity of -Edge Colouring
Esther Galby, Paloma T. Lima, Daniël Paulusma +1
For every fixed integer , we prove that -Edge Colouring is fixed-parameter-tractable when parameterized by the number of vertices of maximum degree.
Graph Isomorphism for -free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski +3
We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs and for all but six pairs $(H_1,H_2)…
Contracting Bipartite Graphs to Paths and Cycles
Konrad K. Dabrowski, Daniël Paulusma
Testing if a given graph contains the -vertex path as a minor or as an induced minor is trivial for every fixed integer . However, the situation changes for t…
Clique-Width for Graph Classes Closed under Complementation
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson +3
Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite)…
Colouring Diamond-free Graphs
Konrad K. Dabrowski, François Dross, Daniël Paulusma
The Colouring problem is that of deciding, given a graph and an integer , whether admits a (proper) -colouring. For all graphs up to five vertices, we classify th…
Bounding the Clique-Width of -free Split Graphs
Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang +1
A graph is -free if it has no induced subgraph isomorphic to . We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new…
Kempe Equivalence of Colourings of Cubic Graphs
Carl Feghali, Matthew Johnson, Daniel Paulusma
Given a graph and a proper vertex colouring of , a Kempe chain is a subset of that induces a maximal connected subgraph of in which every vertex has one of two…
Bounding the Clique-Width of -free Chordal Graphs
Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang +1
A graph is -free if it has no induced subgraph isomorphic to . Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3…
Editing to Eulerian Graphs
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +1
We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let , and denote t…
Bounding Clique-Width via Perfect Graphs
Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma
Given two graphs and , a graph is -free if it contains no subgraph isomorphic to or . We continue a recent study into the clique-width of $(H_1…
Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
Konrad K. Dabrowski, Daniël Paulusma
If a graph has no induced subgraph isomorphic to any graph in a finite family , it is said to be -free. The class of -free graphs has bound…
Classifying the Clique-Width of -Free Bipartite Graphs
Konrad K. Dabrowski, Daniël Paulusma
Let be a bipartite graph, and let be a bipartite graph with a fixed bipartition . We consider three different, natural ways of forbidding as an induced subgr…
Induced Disjoint Paths in Claw-Free Graphs
Petr A. Golovach, Daniel Paulusma, Erik Jan van Leeuwen
Paths P1,...,Pk in a graph G=(V,E) are said to be mutually induced if for any 1 <= i < j <= k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their en…
The k-in-a-path problem for claw-free graphs
Jiri Fiala, Marcin Kaminski, Bernard Lidicky +1
Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial tim…