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 .
A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.
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.
Keywords: latin square
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 ?