Conjecture \item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.
For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.
Conjecture If is a simple digraph without directed cycles of length , then .
Conjecture Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.
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
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 A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
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 .
A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.
Problem Is it true that for every , all but finitely many -regular graphs have friendly partitions?
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 .
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)?
login/create account
, determine whether or not 
, we define 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
-uniform hypergraph on 
vertices which contains no complete 
hyperedges. 
vertices which contains no complete 
hyperedges. ![$ p \in {\mathbb Q}[x] $](/files/tex/a72fcb0a006c3c2afb3ba69722ccdb2599b83e90.png)
rationally derived if all roots of 
and the nonzero derivatives of 
, there exist positive integers 
, 
, 
such that 
.
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
vertices. Is it true that either 
contains a complete bipartite subgraph with bipartition 
so that 
? 
contains every oriented tree of order 
as a subdigraph. 
-manifold has the homotopy type of the 
, is it diffeomorphic to 
be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and 
be the size of the smallest 
, then 
. 
be a circuit in a bridgeless cubic graph 
and 
. Then for any neighborhood 
there is 
such that 
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 
is for every sets 
and 
, for 
if each of the color classes is of size of either 
or 
? ![\[ F_n = 2^{2^n } + 1 \]](/files/tex/0da5a50010e4e5df91c0d58080245ece34ec9ca6.png)
that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
, there exists a constant 
, so that every graph 
. 
, all but finitely many 
, such that 
.
has an acyclic induced subdigraph of order at least 
. 
-regular graph, then there is a symmetric signing of 
entries by 
) so that the resulting matrix has all eigenvalues of magnitude at most 
. 
such that every set of at least 
Drupal
CSI of Charles University