Raphael Yuster's open problems and conjectures in Combinatorics, Graph Theory and Algorithms

The open problems and conjectures listed in this page are mostly suitable for graduate students although prominent researchers may find some of them challenging. Solutions will be posted and appropriate credit will be given to the solver.

Problem 1 (from January 2005)

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 subgraph of H in o(n^k) time?

Problem 2 (from August 2004)

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 is posed in my paper "The number of edge-disjoint transitive triples in a tournament".

Problem 3 (from November 1999)

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 is a construction of a planar graph with f(G)=5. Any improvement upon these upper and lower bounds would be nice.
This problem is studied in my paper with Roditty and Shoham "Monotone paths in edge-ordered sparse graphs".

Problem 4 (from January 1997)

Is there a polynomial time algorithm that decides whether a graph with bounded tree width and with m edges has m/3 edge disjoint paths on three edges?
This problem, which is a special instance of the H-decomposition problem, cannot be expressed in Monadic Second Order Logic. This H-decomposition problem is studied in my paper with Caro "Graph decomposition of slim graphs". It is shown there that for many specific graphs H (including all cliques), the H-decomposition problem can be solved in polynomial time in graphs with bounded tree width. The path with three edges is the smallest H for which this is not known.