5 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…
The role of counting quantifiers in laminar set systems
Rutger Campbell, Noleen Köhler
Laminar set systems consist of non-crossing subsets of a universe with set inclusion essentially corresponding to the descendant relationship of a tree, the so-called laminar tree.…
CMSO-transducing tree-like graph decompositions
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté +2
We give -transductions that, given a graph , output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results…
Bandwidth Parameterized by Cluster Vertex Deletion Number
Tatsuya Gima, Eun Jung Kim, Noleen Köhler +2
Given a graph and an integer , Bandwidth asks whether there exists a bijection from to such that $\max_{\{u, v \} \in E(G)} | Ï(u) - Ï(…
Twin-width one
Jungho Ahn, Hugo Jacob, Noleen Köhler +3
We investigate the structure of graphs of twin-width at most , and obtain the following results: - Graphs of twin-width at most are permutation graphs. In particular they ha…