Pith. sign in

Antidirected trees in dense digraphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

We show that if $D$ is an $n$-vertex digraph with more than $(k-1)n$ arcs that does not contain any of three forbidden digraphs, then $D$ contains every antidirected tree on $k$ arcs. The forbidden digraphs are those orientations of $K_{2, \lceil k/12\rceil}$ where each of the vertices in the class of size two has either out-degree $0$ or in-degree $0$. This proves a conjecture of Addario-Berry et al. for a broad class of digraphs, and generalises a result for $K_{2, \lfloor k/12\rfloor}$-free graphs by Balasubramanian and Dobson. We also show that every digraph $D$ on $n$ vertices with more than $(k-1)n$ arcs contains every antidirected $k$-arc caterpillar, thus solving the above conjecture for caterpillars. This generalises a result of Perles.

fields

math.CO 1

years

2024 1

verdicts

CONDITIONAL 1

representative citing papers

Oriented Trees in Digraphs without Oriented $4$-cycles

math.CO · 2024-11-20 · conditional · novelty 6.0

If a digraph has no oriented 4-cycles, minimum semidegree at least k/2, and at least one vertex with outdegree and indegree at least k, then it contains every oriented tree with k arcs.

citing papers explorer

Showing 1 of 1 citing paper.

  • Oriented Trees in Digraphs without Oriented $4$-cycles math.CO · 2024-11-20 · conditional · none · ref 19 · internal anchor

    If a digraph has no oriented 4-cycles, minimum semidegree at least k/2, and at least one vertex with outdegree and indegree at least k, then it contains every oriented tree with k arcs.