Conjecture   A natural number is a prime iff

Conjecture   Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?

Conjecture   Every even integer greater than 2 is the sum of two primes.

Conjecture   Every graph satisfies .

Conjecture   Let be a digraph all of whose strong components are nontrivial. Then contains a cyclic spanning subdigraph with cyclomatic number at most .

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

Conjecture   If is a tournament of order , then it contains arc-disjoint transitive subtournaments of order 3.

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

Conjecture   Let be the space of Diffeomorphisms on the connected , compact and boundaryles manifold M and the space of vector fields. There is a dense set ( ) such that exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space

Conjecture   Let and . Then for any neighborhood there is such that is periodic point of

Conjecture   In the category of continuous funcoids (defined similarly to the category of topological spaces) the following is a direct categorical product:

\item Product morphism is defined similarly to the category of topological spaces. \item Product object is the sub-atomic product. \item Projections are sub-atomic projections.

Question   Are there graphs for which is arbitrarily large?

Problem   Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?

Conjecture   If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

Conjecture  (BEC-conjecture)   If and are -vertex graphs and , then and pack.

Conjecture   Every k-arc-strong tournament decomposes into k spanning strong digraphs.

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

Problem   Let be positve integer Does there exists an integer such that every -strong tournament admits a partition of its vertex set such that the subtournament induced by is a non-trivial -strong for all .

Conjecture   There is an absolute constant such that for every hexagonal graph and vertex weighting ,

Conjecture   Let be a planar graph of maximum degree . The chromatic number of its square is

\item at most if , \item at most if , \item at most if .