Meike Hatzel
YOU?
Author Swipe
View article: Unavoidable Induced Subgraphs in Graphs with Complete Bipartite Induced Minors
Unavoidable Induced Subgraphs in Graphs with Complete Bipartite Induced Minors Open
International audience
View article: Girth in GF(q)$\textsf {GF}(q)$‐representable matroids
Girth in GF(q)$\textsf {GF}(q)$‐representable matroids Open
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field and any integer , every cosimple ‐representable matroid with sufficiently large girth contains either or as a minor.
View article: Unavoidable butterfly minors in digraphs of large cycle rank
Unavoidable butterfly minors in digraphs of large cycle rank Open
Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function $f:\mathbb{N}\to \mathbb{N}$ such that every digraph of cycle rank at least $f(k)$ contains a directed cycle chain, a …
View article: Odd coloring graphs with linear neighborhood complexity
Odd coloring graphs with linear neighborhood complexity Open
We prove that any class of bipartite graphs with linear neighborhood complexity has bounded odd chromatic number. As a result, if $\mathcal{G}$ is the class of all circle graphs, or if $\mathcal{G}$ is any class with bounded twin-width, bo…
View article: The Erdős-Pósa property for circle graphs as vertex-minors
The Erdős-Pósa property for circle graphs as vertex-minors Open
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or …
View article: Girth in $GF(q)$-representable matroids
Girth in $GF(q)$-representable matroids Open
We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field $GF(q)$ and any integer $t$, every cosimple $GF(q)$-representable matroid with sufficiently large girth contains either $M(K_t)$ or $M(K_t)^*$ as a minor.
View article: On graphs with a simple structure of maximal cliques
On graphs with a simple structure of maximal cliques Open
We say that a hereditary graph class $\mathcal{G}$ is \emph{clique-sparse} if there is a constant $k=k(\mathcal{G})$ such that for every graph $G\in\mathcal{G}$, every vertex of $G$ belongs to at most $k$ maximal cliques, and any maximal c…
View article: Braces of Perfect Matching Width 2
Braces of Perfect Matching Width 2 Open
Perfect matching width is a treewidth-like parameter designed for graphs with perfect matchings. The concept was originally introduced by Norine for the study of non-bipartite Pfaffian graphs. Additionally, perfect matching width appears t…
View article: On graphs coverable by chubby shortest paths
On graphs coverable by chubby shortest paths Open
Dumas, Foucaud, Perez, and Todinca [SIAM J. Disc. Math., 2024] proved that if the vertex set of a graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is bounded by $\mathcal{O}(k \cdot 3^k)$. We prove a coarse variant…
View article: Bounds on treewidth via excluding disjoint unions of cycles
Bounds on treewidth via excluding disjoint unions of cycles Open
One of the fundamental results in graph minor theory is that for every planar graph~$H$, there is a minimum integer~$f(H)$ such that graphs with no minor isomorphic to~$H$ have treewidth at most~$f(H)$. The best known bound for an arbitrar…
View article: Generating strongly 2-connected digraphs
Generating strongly 2-connected digraphs Open
We prove that there exist four operations such that given any two strongly $2$-connected digraphs $H$ and $D$ where $H$ is a butterfly-minor of $D$, there exists a sequence $D_0,\dots, D_n$ where $D_0=H$, $D_n=D$ and for every $0\leq i\leq…
View article: Counterexample to Babai's lonely colour conjecture
Counterexample to Babai's lonely colour conjecture Open
Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large girth and chromatic number …
View article: Erdős-Pósa property of tripods in directed graphs
Erdős-Pósa property of tripods in directed graphs Open
Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$. A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-ve…
View article: Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
Half-integral Erdős-Pósa property for non-null $S$-$T$ paths Open
For a group $Γ$, a $Γ$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $Γ$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null if th…
View article: Computing $\vec{\mathcal{S}}$-DAGs and Parity Games
Computing $\vec{\mathcal{S}}$-DAGs and Parity Games Open
Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiede…
View article: Graphs with at most two moplexes
Graphs with at most two moplexes Open
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples,…
View article: Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Unavoidable induced subgraphs in graphs with complete bipartite induced minors Open
We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a g…
View article: Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem Open
In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas from the mid-nineties. The theorem states the existence of a function $f$ such that every digraph…
View article: On tree decompositions whose trees are minors
On tree decompositions whose trees are minors Open
In 2019, Dvořák asked whether every connected graph has a tree decomposition so that is a subgraph of and the width of is bounded by a function of the treewidth of . We prove that this is false, even when has treewidth 2 and is allowed to …
View article: Decomposition of (infinite) digraphs along directed 1-separations
Decomposition of (infinite) digraphs along directed 1-separations Open
We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the structure of finite and infinite directed graphs with respec…
View article: On tree decompositions whose trees are minors
On tree decompositions whose trees are minors Open
In 2019, Dvořák asked whether every connected graph $G$ has a tree decomposition $(T, \mathcal{B})$ so that $T$ is a subgraph of $G$ and the width of $(T, \mathcal{B})$ is bounded by a function of the treewidth of $G$. We prove that this i…
View article: Tight bound on treedepth in terms of pathwidth and longest path
Tight bound on treedepth in terms of pathwidth and longest path Open
We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor.
View article: Simpler and faster algorithms for detours in planar digraphs
Simpler and faster algorithms for detours in planar digraphs Open
In the directed detour problem one is given a digraph $G$ and a pair of vertices $s$ and~$t$, and the task is to decide whether there is a directed simple path from $s$ to $t$ in $G$ whose length is larger than $\mathsf{dist}_{G}(s,t)$. Th…
View article: Tuza's Conjecture for Threshold Graphs
Tuza's Conjecture for Threshold Graphs Open
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average de…
View article: Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation Open
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s…
View article: Constant Congestion Brambles
Constant Congestion Brambles Open
A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H…
View article: Graphs with at most two moplexes
Graphs with at most two moplexes Open
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. While every non-complete graph has at least two moplexes, little is known about structural properties of graphs…
View article: Tuza's Conjecture for Threshold Graphs
Tuza's Conjecture for Threshold Graphs Open
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average de…