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.
Detecting small complete hypergraphs.
For k > r > 2 let K(k,r) denote the complete
r-uniform hypergraph with k vertices. Is there an algorithm that,
given an r-uniform hypergraph H with n vertices, decides whether
K(k,r) is a sub-hypergraph of H in o(nk-ε)
time? The answer is well-known for r=2 (graphs) but already the first nontrivial
hypergraph case of r=3 and k=4 is open.
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. Any improvement upon these upper and lower bounds would be nice.
See the following paper for more information.
