wovepaper · research, woven together

papers

Publications (9)

math.CO2024

Aharoni's rainbow cycle conjecture holds up to an additive constant

Patrick Hompe, Tony Huynh

In 2017, Aharoni proposed the following generalization of the Caccetta-HÃ¤ggkvist conjecture: if $G$ is a simple $n$ -vertex edge-colored graph with $n$ color classes of size at lea…

math.CO2022

Digraphs with all induced directed cycles of the same length are not $I ¨ $ -bounded

Alvaro Carbonero, Patrick Hompe, Benjamin Moore +1

For $t \geq 2$ , let us call a digraph $D$ \emph{t-chordal} if all induced directed cycles in $D$ have length equal to $t$ . In a previous paper, we asked for which $t$ it is true tha…

math.CO2022

Some results on concatenating bipartite graphs

Patrick Hompe

We consider two functions $I ¨ $ and $I ¨ $ , defined as follows. Let $x, y \in (0, 1]$ and let $A, B, C$ be disjoint nonempty subsets of a graph $G$ , where every vertex in $A$ has at least…

math.CO2020

Concatenating bipartite graphs

Maria Chudnovsky, Patrick Hompe, Alex Scott +2

Let $x, y \in (0, 1]$ and let $A, B, C$ be disjoint nonempty subsets of a graph $G$ , where every vertex in $A$ has at least $x ∣ B ∣$ neighbours in $B$ , and every vertex in $B$ has at least…

math.CO2022

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Alvaro Carbonero, Patrick Hompe, Benjamin Moore +1

We prove that for every $n$ , there is a graph $G$ with $I ¨ (G) \geq n$ and $I ¨ (G) \leq 3$ such that every induced subgraph $H$ of $G$ with $I ¨ (H) \leq 2$ satisfies $I ¨ (H) \leq 4$ . T…

math.CO2023

Further approximations for Aharoni's rainbow generalization of the Caccetta-HÃ¤ggkvist conjecture

Patrick Hompe, Sophie Spirkl

For a digraph $G$ and $v \in V (G)$ , let $I^´^{+} (v)$ be the number of out-neighbors of $v$ in $G$ . The Caccetta-HÃ¤ggkvist conjecture states that for all $k \geq 1$ , if $G$ is a digrap…

Publications (9)

Aharoni's rainbow cycle conjecture holds up to an additive constant

Digraphs with all induced directed cycles of the same length are not I¨-bounded

Some results on concatenating bipartite graphs

Concatenating bipartite graphs

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Further approximations for Aharoni's rainbow generalization of the Caccetta-HÃ¤ggkvist conjecture

Digraphs with all induced directed cycles of the same length are not $I ¨ $ -bounded