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.

Conjecture   Let $ D $ be a digraph. If $ |A(D)| > (k-2) |V(D)| $, then $ D $ contains every antidirected tree of order $ k $.

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 $ c<4 $, there is only a finite number of good-edge-labeling critical graphs with average degree less than $ c $.

Keywords: good edge labeling, edge labeling

Syndicate content