Source author record

Patrick Hompe

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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

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 disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5.

preprint2022arXiv

Proof of the Caccetta-Haggkvist conjecture for digraphs with small independence number

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 \ge 1$ , if $G$ is a digraph with $n = |V(G)|$ such that $δ^+(v) \ge n/k$ for all $v \in V(G)$ , then G contains a directed cycle of length at most $k$ . In [2], N. Lichiardopol proved that this conjecture is true for digraphs with independence number equal to two. In this paper, we generalize that result, proving that the conjecture is true for digraphs with independence number at most $(k+1)/2$ .

preprint2022arXiv

Some results on concatenating bipartite graphs

We consider two functions $ϕ$ and $ψ$ , 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 $x|B|$ neighbors in $B$ , and every vertex in $B$ has at least $y|C|$ neighbors in $C$ . We denote by $ϕ(x,y)$ the maximum $z$ such that, in all such graphs $G$ , there is a vertex $v \in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. If in addition we require that every vertex in $B$ has at least $x|A|$ neighbors in $A$ , and every vertex in $C$ has at least $y|B|$ neighbors in $C$ , we denote by $ψ(x,y)$ the maximum $z$ such that, in all such graphs $G$ , there is a vertex $v \in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. In their recent paper, M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl introduced these functions, proved some general results about them, and analyzed when they are greater than or equal to $1/2, 2/3,$ and $1/3$ . Here, we extend their results by analyzing when they are greater than or equal to $3/4, 2/5,$ and $3/5$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Patrick Hompe

Research overview

Is this your work?

3 publications

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

Proof of the Caccetta-Haggkvist conjecture for digraphs with small independence number

Some results on concatenating bipartite graphs

See the researcher in context

Building this map preview