6 citations · 6 across the 2 of their papers we have counts for
7 papers · 1 filter
Complexity Classification of Colouring Problems with Parity Constraints
Rémy Belmonte, Juan Pablo Bravo, Noleen Köhler +1
We study variants of graph colouring with parity constraints. More specifically, we consider -colourings of a graph where, for every…
Parameterized Complexity of -Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki +6
Given a graph , , and integers and , the \textsc{-Path Packing} problem asks to find vertex-disjoint paths of length that h…
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for g…
Token Sliding on Split Graphs
Rémy Belmonte, Eun Jung Kim, Michael Lampis +3
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked i…
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is…
Parameterized (Approximate) Defective Coloring
Rémy Belmonte, Michael Lampis, Valia Mitsou
In Defective Coloring we are given a graph and two integers and are asked if we can partition into color classes, so that each class induces a gra…