Long path in Eulerian directed graphs.
Is it true that any simple Eulerian digraph with n vertices and m arcs has a simple
path of length Ω(m/n)?
See the following paper for more information.
Packing regular tournaments with small cycles.
Is it true that any regular tournament with n vertices has (1-o(1))n^2/8 arc-disjoint
cycles of length 4?
Is it true that any regular tournament with n vertices has (1-o(1))n^2/9 arc-disjoint
cycles of length 3?
See the following paper for more information.
Packing transitive triples in a tournament.
Conjecture: Every tournament with n vertices contains a set of at least n(n-1)/6
- n/3 edge-disjoint transitive tournaments on three vertices. This has been verified
for all n < 9. The conjecture appears here.
Monotone paths in planar graphs.
For a simple undirected graph G, let f(G) be the minimum over all edge orderings
of the maximum length of a monotone path. It is known that if G is planar then f(G)
≤ 9. There are constructions of planar
graphs with f(G)=6.
See the following paper for more information.
