A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Conjecture Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .
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 ?
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 .
Problem Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.
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 Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members 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,
Conjecture Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?
Conjecture Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.
In particular, this implies:
Conjecture Twin Prime Conjecture: There are an infinite number of twin primes.
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 ?
login/create account
-flow 
on 
is an orientation 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
is a class 1 graph if its edge chromatic number is 
be an integer and 
-regular graph. If 
. 
. 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
of edges such that every vertex is incident to exactly one edge from 
-connected finite graph, is there an assignment of lengths 
to the edges of 
-geodesic cycle is 
does there exists a 
such that every graph with average degree smaller than 
if 
is odd and 
if 
. Assume we start with some number 
of the current number. Prove that no matter what the initial number is we eventually reach 
. 
be a prime natural number. Find all primes 
, such that 
.
and 
be two 
. Does there always exist a partition of 
such that for both 
, at least 
hyperedges of 
meet each of the classes 
so that every abelian group 
with 
so that the 
has no clique or independent set of size 
. 
and 
. It is equivalent to a homomorphism of the digraph onto some tournament of order ![\[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]](/files/tex/d2391343543ce03d861e6eb2f4985d52e309525d.png)
. 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
for 
. 
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)
edges whose deletion destroys every triangle. 
be a sequence of points in 
with the property that for every 
, the points 
are distinct, lie on a unique sphere, and further, 
is the center of this sphere. If this sequence is periodic, must its period be 
? 
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
, the family of graphs with no induced subgraph isomorphic to 
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 
? 
there is 
such that, for every large 
and 
. 
has chromatic number at most 
.
Drupal
CSI of Charles University