Open problems, a collection

There are often many different ways to state the same problem, some catch the full generality, and some highlight a particularly easy to state / hard to prove instance. I chose this last way here, trying to fit to a one-line statement starting by "Every". Few additional notes and definitions may be found in the more link. Needless to say, this site is by definition under construction.

  • Tutte's 5-flow conjecture:
    Every bridgeless graph G has an orientation G' such that e(X,Y)/5≤e'(X,Y) for every vertex-partition (X,Y). more
  • The Cacceta-Häggkvist conjecture:
    Every oriented graph on n vertices with minimum outdegree n/3 has a circuit of length 3. more
  • The seagull conjecture:
    Every graph on n vertices with stability 2 has a complete matching of size c.n, for some fixed c>0. more
  • The cycle double cover conjecture:
    Every bridgeless graph has a set of cycles which covers every edge twice. more
  • Woodall's planar girth conjecture:
    Every planar directed graph has g disjoint feedback arc sets, where g is the minimum length of a circuit . more
  • Long paths in oriented graphs:
    Every oriented graph with minimum outdegree δ+ has a directed path of length 2δ+. more
  • Hedetniemi's conjecture:
    Every categorical product of two k-chromatic graphs is k-chromatic. more
  • Seymour's second neighborhood conjecture:
    Every oriented graph has a vertex with second outneighborhood at least as large as the first. more
  • Acyclic partitions of planar digraphs:
    Every oriented planar graph has a vertex-partition into two acyclic induced subgraphs. more
  • Stiebitz's degree partition conjecture:
    Every digraph with large δ+ has a vertex-partition into two digraphs with δ+ at least 2. more
  • Ramsey for excluded induced subgraphs:
    Every n-graph not inducing a fixed graph G has a clique or a stable set of size nε, where ε>0 depends of G.
  • Frankl's union-closed sets conjecture:
    Every set of subsets which is closed under union has an element which belongs to at least half of these sets.
  • Cyclic enumeration of matroids:
    Every union of two disjoint basis has a cyclic enumeration such that every cyclic half-interval is a basis.
  • Czerný's conjecture:
    Every n-state synchronizing automaton has a synchronizing word of length at most (n-1)^2.