6 citations · 19 across the 12 of their papers we have counts for
17 papers
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…
Odd Chromatic Number of Graph Classes
Rémy Belmonte, Ararat Harutyunyan, Noleen Köhler +1
A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, o…
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…
Grundy Distinguishes Treewidth from Pathwidth
Rémy Belmonte, Eun Jung Kim, Michael Lampis +2
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to und…
On the complexity of finding large odd induced subgraphs and odd colorings
Rémy Belmonte, Ignasi Sau
We study the complexity of the problems of finding, given a graph , a largest induced subgraph of with all degrees odd (called an odd subgraph), and the smallest number of o…
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…