![](/files/happy5.png)
Havet, Frédéric
Erdős-Posa property for long directed cycles ★★
Conjecture Let
be an integer. For every integer
, there exists an integer
such that for every digraph
, either
has a
pairwise-disjoint directed cycles of length at least
, or there exists a set
of at most
vertices such that
has no directed cycles of length at least
.
![$ \ell \geq 2 $](/files/tex/061b4d40c28de2de3ccfebdeeb52a6730a9cee76.png)
![$ n\geq 0 $](/files/tex/6a9c6e677c8a074e2f8306290b3acb959626d2a4.png)
![$ t_n=t_n(\ell) $](/files/tex/2ce8e7dd4d72ec3247e3b656a3e3cfa985241df5.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \ell $](/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ t_n $](/files/tex/4e1d881c711abbf6021a83fe432d28abc22d717b.png)
![$ D-T $](/files/tex/15b90efb84c80a9728144fa55150c691b4230a8a.png)
![$ \ell $](/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png)
Keywords:
Antidirected trees in digraphs ★★
Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé
An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.
Conjecture Let
be a digraph. If
, then
contains every antidirected tree of order
.
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ |A(D)| > (k-2) |V(D)| $](/files/tex/9d92913ac31fe6777abefdb2c40e6ec0c94bcf8a.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
Keywords:
Good Edge Labelings ★★
Author(s): Araújo; Cohen; Giroire; Havet
Question What is the maximum edge density of a graph which has a good edge labeling?
We say that a graph is good-edge-labeling critical, if it has no good edge labeling, but every proper subgraph has a good edge labeling.
Conjecture For every
, there is only a finite number of good-edge-labeling critical graphs with average degree less than
.
![$ c<4 $](/files/tex/88cd640bb1356a23eb073fd0b147a9a1bca21999.png)
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
Keywords: good edge labeling, edge labeling
![Syndicate content Syndicate content](/misc/feed.png)