33 citations · 101 across the 16 of their papers we have counts for
21 papers
Certifying coloring algorithms for graphs without long induced paths
Marcin Kamiński, Anna Pstrucha
Let be a path, a cycle on vertices, and a complete bipartite graph with vertices on each side of the bipartition. We prove that (1) for any integers $…
Well-quasi-ordering H-contraction-free graphs
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck
A well-quasi-order is an order which contains no infinite decreasing sequence and no infinite collection of incomparable elements. In this paper, we consider graph classes defined…
The Price of Connectivity for Feedback Vertex Set
Rémy Belmonte, Pim van 't Hof, Marcin Kamiński +1
Let fvs and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph , respectively. The price of connectivi…
Induced minors and well-quasi-ordering
Jarosław Błasiok, Marcin Kamiński, Jean-Florent Raymond +1
A graph is an induced minor of a graph if it can be obtained from an induced subgraph of by contracting edges. Otherwise, is said to be -induced minor-free. Robi…
The Parameterized Complexity of Graph Cyclability
Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis +1
The cyclability of a graph is the maximum integer for which every vertices lie on a cycle. The algorithmic version of the problem, given a graph and a non-negative inte…
Multigraphs without large bonds are wqo by contraction
Marcin Kamiński, Jean-Florent Raymond, Théophile Trunck
We show that the class of multigraphs with at most connected components and bonds of size at most is well-quasi-ordered by edge contraction for all positive integers .…