5 citations · 6 across the 7 of their papers we have counts for
11 papers
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.…
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…
CMSO-transductions for 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…
Core Stability in Additively Separable Hedonic Games of Low Treewidth
Tesshu Hanaka, Noleen Köhler, Michael Lampis
Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent selfish agents and the weight of each edge denot…
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) - π(v)…
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…
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…
Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3
We introduce the notion of delineation. A graph class is said delineated if for every hereditary closure of a subclass of , it holds that $\ma…
GSF-locality is not sufficient for proximity-oblivious testing
Isolde Adler, Noleen Köhler, Pan Peng
In Property Testing, proximity-oblivious testers (POTs) form a class of particularly simple testing algorithms, where a basic test is performed a number of times that may depend on…
An explicit construction of graphs of bounded degree that are far from being Hamiltonian
Isolde Adler, Noleen Köhler
Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonia…
On Testability of First-Order Properties in Bounded-Degree Graphs
Isolde Adler, Noleen Köhler, Pan Peng
We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree graph and relational structure models. We show that any FO property that…