1 citations · 6 across the 31 of their papers we have counts for
9 papers · 1 filter
Hamiltonian connectivity of some base-cobase graphs
Leonardo Martínez-Sandoval, Kolja Knauer
There has been wide interest in understanding which properties of base graphs of matroids extend to base-cobase graphs of matroids. A significant result of Naddef and Pulleyblank (…
What is and is not inside a Cayley graph?
Kolja Knauer, Alvaro Soto Gomez
In this note we show that there is a cubic graph of girth that is not a subgraph of any minimal Cayley graph. On the other hand, we show that any Generalized Petersen Graph $G(…
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…
Strong odd coloring in minor-closed classes
Miriam Goetze, Fabian Klute, Kolja Knauer +3
We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.
Cell structure of mediangle graphs
Victor Chepoi, Anthony Genevois, Kolja Knauer
Mediangle graphs are a common generalization of median graphs (1-sekeleta of CAT(0) cube complexes) and Coxeter graphs (Cayley graphs of Coxeter systems). Answering a question moti…
Sensitivity and Hamming graphs
Sara Asensio, Yuval Filmus, Ignacio García-Marco +1
For any we show that the Hamming graph admits an imbalanced partition into sets, each inducing a subgraph of low maximum degree. This improves previous resul…
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…
Shellability of the quotient order on lattice path matroids
Carolina Benedetti, Anton Dochtermann, Kolja Knauer +1
The concept of a matroid quotient has connections to fundamental questions in the geometry of flag varieties. In previous work, Benedetti and Knauer characterized quotients in the…
On rigid regular graphs and a problem of Babai and Pultr
Kolja Knauer, Gil Puig i Surroca
A graph is \textit{rigid} if it only admits the identity endomorphism. We show that for every there exist infinitely many mutually rigid -regular graphs of arbitrary od…