An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours and . It is equivalent to a homomorphism of the digraph onto some tournament of order .
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 .
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:
\item \item
where is a fixed recursive set of integers.
Let us fix and a closed formula in this language.
Conjecture Is it true that the validity of for a graph of tree-width at most can be tested in polynomial time in the size of ?
Conjecture For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .
The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
Conjecture If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .
Problem What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?
Conjecture For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .
Problem Is it true for all , that every sufficiently large -connected graph without a minor has a set of vertices whose deletion results in a planar graph?
login/create account
of colours to the vertices such that no two arcs receive ordered pairs of colours 
and 
. It is equivalent to a homomorphism of the digraph onto some tournament of order 
.
be a graph and 
. The graph 
is defined to be the 
-power of the 
-subdivision of 
.
. Then 
. 
with 
so that the 
has no clique or independent set of size 
. 
\item 
is a fixed recursive set of integers.
in this language.
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
be an abelian group. Is the 
such that if 
is a digraph whose arcs are colored with 
set which is the union of 
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?
.
, the union of any 
-degenerate graph. 
. 
is a finite field with at least 4 elements and 
which have no coordinates equal to zero such that 
. 
. 
has a cycle with length at most 
denote the 
-dimensional cube graph. A map 
is called edge-antipodal if 
whenever 
are antipodal edges. 
and 
which are joined by a monochromatic path. 
be integers. Set 
and 
for 
. Eventually we have 
; put 
.
, since 
, 
, 
, 
, 
, 
, 
, 
.
.
concentrated on a single value? 
-graph if it has a bipartition 
so that every vertex in 
and every vertex in 
. 
, then 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
can be represented as the sum of an odd prime number and an odd 
. 
and graph 
. 
is for every sets 
and 
and 
are 
-
, that every sufficiently large 
vertices whose deletion results in a 
Drupal
CSI of Charles University