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?
Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.
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 .
Question \item Does hold over graphs of bounded tree-width? \item Is included in over graphs? \item Does have a 0-1 law? \item Are properties of Hanf-local? \item Is there a logic (with an effective syntax) that captures ?
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
A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .
Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .
Question Does the Blatter-Specker Theorem hold for ternary relations.
Problem Let and be two -uniform hypergraph on the same vertex set . Does there always exist a partition of into classes such that for both , at least hyperedges of meet each of the classes ?
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
Conjecture Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?
Conjecture For all positive integers and , there exists an integer such that every graph of average degree at least contains a subgraph of average degree at least and girth greater than .
Problem Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .
Conjecture If in a bridgeless cubic graph the cycles of any -factor are odd, then , where denotes the oddness of the graph , that is, the minimum number of odd cycles in a -factor of .
Conjecture A total coloring of a graph is an assignment of colors to the vertices and the edges of such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph , , equals the minimum number of colors needed in a total coloring of . It is an old conjecture of Behzad that for every graph , the total chromatic number equals the maximum degree of a vertex in , plus one or two. In other words,
login/create account
denote the 
diagonal 
exists. 
rectangular 
-dimensional boxes each of which has side lengths 
inside an 
? 
has chromatic number at most 
. 
-neighbour bootstrap process in the hypercube. 
be a positive integer. We say that a graph 
is strongly 
is the maximal degree of a graph 
-colorable. 
is the only 
there is an integer 
such that every digraph of minimum outdegree at least 
does there exists a 
such that every graph with average degree smaller than 
hold over graphs of bounded tree-width? \item Is 
included in 
over graphs? \item Does 
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 
such that every 
-minor-free graph has at most 
cliques? 
for every 
with odd size.
for every 
is the minimum number of colours in a strong edge-colouring of 
be a class of finite relational structures. We denote by 
the number of structures in 
. For any class 
, the function 
. 
can be represented as the sum of an odd prime number and an odd ![\[ F_n = 2^{2^{n } } + 1 \]](/files/tex/70ca73d7e82af2fee084a8417e172c58cf78b376.png)
Square-Free?
and 
be two 
. Does there always exist a partition of 
such that for both 
, at least 
hyperedges of 
meet each of the classes 
-factor in a graph 
contains and 
, every 
vertices has a Hamilton cycle. 
and 
and let 
be a surface. Is it true that every optimal drawing of 
has an acyclic induced subdigraph of order at least 
. 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
-connected planar graph, then 
has a Hamilton cycle. 
-factor are odd, then 
, where 
denotes the oddness of the graph 
is an assignment of colors to the vertices and the edges of 
, equals the minimum number of colors needed in a total coloring of 
plus one or two. In other words, ![\[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]](/files/tex/d4ea30e930ec20e02c5a03c6322e6d99a6bdb63a.png)
let 
. 
be a matroid on 
, let 
be a map, put 
and 
. Then 
be the unique integer (with respect to a fixed 
) such that
is a prime iff ![$$ \displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor $$](/files/tex/99af565f4cc4d3bab11eb3fbf54f78626678d484.png)
such that 
or prove that such integers do not exist. 
Drupal
CSI of Charles University