Patrick Hompe

activity

20192022

most citedAharoni's rainbow cycle conjecture holds up to an additive constant

2 citations · 8 across the 8 of their papers we have counts for

collaborators

Showing 2022Show all

4 papers · 1 filter

math.CO2022★ 2 cited

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 leas…

math.CO2022★ 1 cited

Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Patrick Hompe, Zishen Qu, Sophie Spirkl

For a digraph $G$ and $v \in V (G)$ , let $δ^{+} (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 digraph…

math.CO2022★ 1 cited

Digraphs with all induced directed cycles of the same length are not $χ$ -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★ 1 cited

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 $χ (G) \geq n$ and $ω (G) \leq 3$ such that every induced subgraph $H$ of $G$ with $ω (H) \leq 2$ satisfies $χ (H) \leq 4$ . This…

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

Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Digraphs with all induced directed cycles of the same length are not χ​-bounded

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

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