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 .
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 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 .
Conjecture If a finite set of unit balls in is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.
Conjecture Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .
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.
Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.
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 ?
Problem Does the following equality hold for every graph ?
The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number, we minimize the number of pairs of edges that cross.
Conjecture Let be a graph and be a positive integer. The power of , denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also subdivision of , denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have . Now we can define the fractional power of a graph as follows: Let be a graph and . The graph is defined by the power of the subdivision of . In other words . Conjecture. Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have . In [1], it was shown that this conjecture is true in some special cases.
Problem has the homotopy-type of a product space where is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of .
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.
login/create account
is a simple triangle-free graph, then there is a set of at most 
edges whose deletion destroys every odd cycle. 
is 2-large, then 
is the minimum number of colours in a strong edge-colouring of 
vertices, then 
for 
. 
and 
, there exists an integer 
such that every graph of average degree at least 
is prime and 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease. 
be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of 
-graph if it has a bipartition 
so that every vertex in 
and every vertex in 
has degree 
. 
such that the list chromatic number of any bipartite graph 
is at most 
.
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
of a graph 
, we minimize the number of pairs of edges that cross. 
is defined to be 
where 
is the number of faces of 
.
power of 
, is defined on the vertex set 
, by connecting any two distinct vertices 
and 
with distance at most 
. Also 
, is constructed by replacing each edge 
of 
, we have 
.
. The graph 
is defined by the 
power of the 
subdivision of 
.
and 
be a positive integer greater than 1. Then for any positive integer 
, we have 
.
of co-prime positive integers 
for 
. 
has the homotopy-type of a product space 
where 
is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of 
if 
, \item at most 
if 
, \item at most 
if 
. 
, then 
cycles of length 
. ![$ p \in {\mathbb Q}[x] $](/files/tex/a72fcb0a006c3c2afb3ba69722ccdb2599b83e90.png)
rationally derived if all roots of 
, and let 
be the edge set of a forest chosen uniformly at random from all forests of ![\[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]](/files/tex/1fe7ac9c579238670e3aa16ae401e8194e1c3da3.png)
Drupal
CSI of Charles University