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?
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 An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.
Conjecture Let and are monovalued, entirely defined funcoids with . Then there exists a pointfree funcoid such that (for every filter on ) (The join operation is taken on the lattice of filters with reversed order.)
A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.
Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .
Conjecture For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.
Question What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?
If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .
Problem Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?
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 Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.
Conjecture It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?
Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.
Conjecture For every finite family of graphs there exists an such that .
Conjecture Suppose with is a connected cubic graph admitting a -edge coloring. Then there is an edge such that the cubic graph homeomorphic to has a -edge coloring.
A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.
One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.
The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .
Let be the graph obtained by subdividing each edge of exactly once.
Conjecture There is a function such that for every graph ,
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 For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .
Conjecture For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.
login/create account
-connected cubic graph on 
vertices admit a partition into 
paths of length 
? 
is called double-critical, if removing any pair of adjacent vertexes lowers the 
is the only 
-chromatic double-critical graph 
and 
are monovalued, entirely defined funcoids with 
. Then there exists a pointfree funcoid 
such that (for every filter 
on 
) 
(The join operation is taken on the lattice of filters with reversed order.) 
be a set of points in the plane. Two points 
and 
in 
there is an integer 
collinear points or 
such that every set of at least 
. The graph 
is defined to be the 
-power of the 
.
. Then 
. 
paths. 
are graphs, a function 
is called cycle-continuous if the pre-image of every element of the (binary) cycle space of 
so that there is no cycle continuous mapping between 
and 
whenever 
? 
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. 
(along the track) away from every other runner. 
of graphs and an integer 
of 
such that 
.
is a connected cubic graph admitting a 
such that the cubic graph homeomorphic to 
has a 
of 
and a (non-proper) 
such that edges with the same colour do not cross with respect to 
for some edges 
, then 
and 
receive distinct colours. 
is the minimum integer 
be the graph obtained by subdividing each edge of 
such that for every graph 
a countable end of 
an infinite set of pairwise disjoint 
of pairwise disjoint 
be a set of ![\[m(A) = - \min_x \sum_{a \in A} \cos(ax).\]](/files/tex/7a772ebd0b7fd98eeab7fda3a5e9674b1dc4c984.png)
What is 
? 
be an integer and let 
denote the least integer 
-neighbour bootstrap process in the hypercube. 
. 
, so that every graph 
. 
so that every polytope of dimension 
has a 
Drupal
CSI of Charles University