Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?
Conjecture Let and . Then for any neighborhood there is such that is periodic point of
There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for
Conjecture Let be an -uniform-partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .
Conjecture For every rational and every rational , there is no polynomial-time algorithm for the following problem.
Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.
Conjecture Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.
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 Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
Conjecture Let be a -connected cubic graph and let be a -regular subgraph such that is connected. Then has a cycle double cover which contains (i.e all cycles of ).
login/create account
and 
. Then for any neighborhood 
there is 
such that 
is periodic point of 
vector fields . In the case of diffeos this was proved by Charles Pugh for 
. In the case of Flows this has been solved by Sushei Hayahshy for 
and 
are 
-vertex graphs and 
, then 
cycles. 
are invertible 
matrices with entries in 
for a prime 
submatrix 
of ![$ [B_1 B_2 \ldots B_p] $](/files/tex/86661dc2948aeca789b4392c2e2a9cbf7d96f735.png)
so that 
be an 
-
is the maximum number of pairwise disjoint edges in 
is the size of the smallest set of vertices which meets every edge, then 
. 
such that its fundamental group has an element of finite order?
, we define 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
and every rational 
, there is no polynomial-time algorithm for the following problem.
on 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
. In other words, simplify this formula. 
for some constant 
? 
so that the power series 
is bounded for all 
. 
paths. 
, there exists 
so that every simple 
has a 
. 
be positve integer Does there exists an integer 
such that every 
admits a partition 
of its vertex set such that the subtournament induced by 
is a non-trivial 
-strong for all 
. 
, determine whether or not 
Square free? 
. The representation function 
for 
is given by the rule 
. We call 
is never 
.
, it is impossible to cover a square of side greater than 
unit squares. 
? 
. Suppose that 
and each vertex of 
colors. Then at least 
vertices of 
-connected cubic graph and let 
be a 
is connected. Then 
people admits a solution is 
. ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
Drupal
CSI of Charles University