4 citations · 6 across the 12 of their papers we have counts for
5 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…
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)…