22 citations · 107 across the 16 of their papers we have counts for
4 papers · 1 filter
Linear kernels for edge deletion problems to immersion-closed graph classes
Archontia C. Giannopoulou, Michał Pilipczuk, Dimitrios M. Thilikos +2
Suppose is a finite family of graphs. We consider the following meta-problem, called -Immersion Deletion: given a graph and integer , decide wheth…
Tight lower bounds for the complexity of multicoloring
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2
In the multicoloring problem, also known as (:)-coloring or -fold coloring, we are given a graph G and a set of colors, and the task is to assign a subset of color…
Cutwidth: obstructions and algorithmic aspects
Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond +2
Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges betw…
Square-free graphs are multiplicative
Marcin Wrochna
A graph K is square-free if it contains no four-cycle as a subgraph. A graph K is multiplicative if GxH -> K implies G -> K or H -> K, for all graphs G,H. Here GxH is the tensor (o…