Havet, Frédéric

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.

\begin{conjecture} Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$, then $D$ contains every antidirected tree of order $k$. \end{conjecture}


Good Edge Labelings ★★

Author(s): Araújo; Cohen; Giroire; Havet

\begin{question} What is the maximum edge density of a graph which has a good edge labeling? \end{question}

We say that a graph is \emph{good-edge-labeling critical}, if it has no good edge labeling, but every proper subgraph has a good edge labeling.

\begin{conjecture} For every $c<4$, there is only a finite number of good-edge-labeling critical graphs with average degree less than $c$. \end{conjecture}

Keywords: good edge labeling, edge labeling

Syndicate content