Conjecture   If is a -regular directed graph with no parallel arcs, then contains a collection of arc-disjoint directed cycles.

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Conjecture   There is a constant such that the list chromatic number of any bipartite graph of maximum degree is at most .

Problem   Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?

Conjecture   For every bridgeless graph there is a collection of cycles in that

• covers every edge of and
• has total length at most .

Conjecture   For every and every positive integer , there exists so that every simple -regular graph with has a -regular subgraph with .

Conjecture   For every positive even integer , the number of even latin squares of order and the number of odd latin squares of order are different.

Conjecture   There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .

Conjecture   If is a simple graph which can be written as an union of edge-disjoint complete bipartite graphs, then .

Question   Does there exists a fixed function so that every planar graph of maximum degree has a partition of its vertex set into at most three sets so that for , every component of the graph induced by has size at most ?