1 citations · 1 across the 7 of their papers we have counts for
9 papers
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3
We introduce a new notion of distance between two graph states and on the same set of qubits. This distance is the minimum number of ancilla qubits in a gr…
Biclique decompositions from Welzl orders
Jean Cardinal, Rose McCarty, Yelena Yuditsky
A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of ev…
The Structure of Circle Graph States
Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup +1
Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computat…
The structure of group-labeled graphs forbidding an immersion
Rose McCarty, Caleb McFarland, Paul Wollan
A -labeled graph is an oriented graph with edges invertibly labeled by a group . We prove a structure theorem for -labeled graphs which forbid a fixed -labeled graph as…
Graphs whose Eulerian trails have unique labels
Donggyu Kim, Rose McCarty, Caleb McFarland
Consider an undirected graph whose edges are labeled invertibly in a group. When does every Eulerian trail from one fixed vertex to another have the same label? We give a precise s…
Excluding a clique or a biclique in graphs of bounded induced matching treewidth
Tara Abrishami, Marcin Briański, Jadwiga Czyżewska +4
For a tree decomposition of a graph , let denote the maximum size of an induced matching in with the property that some bag of c…
On classes of bounded tree rank, their interpretations, and efficient sparsification
Jakub Gajarský, Rose McCarty
Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generaliz…
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…