6 papers
Odd coloring graphs with linear neighborhood complexity
James Davies, Meike Hatzel, Kolja Knauer +2
We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if is the class of all circle graphs, or…
The Structural Complexity of Matrix-Vector Multiplication
Emile Anand, Jan van den Brand, Rose McCarty
We consider the problem of preprocessing an matrix , and supporting queries that, for any vector , returns the matrix-vector product . This…
Quantum Graph States: Bridging Classical Theory and Quantum Innovation, Workshop Summary
Eric Chitambar, Kenneth Goodenough, Otfried Gühne +5
This workshop brought together experts in classical graph theory and quantum information science to explore the intersection of these fields, with a focus on quantum graph states a…
The ErdÅs-Pósa property for circle graphs as vertex-minors
Rutger Campbell, J. Pascal Gollin, Meike Hatzel +4
We prove that for any circle graph with at least one edge and for any positive integer , there exists an integer so that every graph either has a vertex-minor…
Girth in -representable matroids
James Davies, Meike Hatzel, Kolja Knauer +2
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field and any integer , every cosimple -representable matroid with sufficiently large gi…
Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
James Davies, Agelos Georgakopoulos, Meike Hatzel +1
In this paper, we consider the class of sphere intersection graphs in for . We show that for each integer , the class of all graphs in $…