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 There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .
The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.
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 If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.
Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is
Problem What is the best upper bound on circular choosability for planar graphs?
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.
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 .
Problem () Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture () Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.
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 .
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 .
Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?
login/create account
, there is only a finite number of good-edge-labeling critical graphs with average degree less than 
. 
such that every planar graph has obstacle number at most 
and 
such that every graph of average degree at least 
. 
appears once in Pascal's triangle, 
appears twice, 
appears three times, and 
appears 
times. There are infinite families of numbers known to appear 
times is 
. It is not known whether any number appears more than 
. See 
be a circuit in a bridgeless cubic graph 
. Then there is a five cycle double cover of 
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. ![\[ M_n = 2^p - 1 \]](/files/tex/eb18a56e5c2e8b1be6ac733d217c0c1f1a47a94e.png)
that is prime.
be an elliptic curve over a number field 
. Then the order of the zeros of its 
-function, 
, at 
is the Mordell-Weil rank of 
. 
there is 
such that, for every large 
, there are 
such that 
and 
. 
. 
is not an integer. 
to the edges of 
-geodesic cycle is 
be a graph. If 
and 
are two integers, a 
-colouring of 
to 
such that 
for each edge 
. Given a list assignment 
a set of non-negative integers, an 
such that 
for every 
. A list assignment 
-
and 
for each vertex 
. Given such a list assignment 
, the graph 
is a 
for all primes 
, where 
is prime. 
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. 
of graphs and an integer 
of 
such that there exists a graph on 
such that 
.
? 
) Find a sufficient condition for a straight 
) Let 
is externally connected, for some 
. Then the graph 
is rearrangeable. 
? 
if 
if 
. Assume we start with some number 
of the current number. Prove that no matter what the initial number is we eventually reach 
is the minimum number of colours in a strong edge-colouring of 
, it is impossible to cover a square of side greater than 
unit squares. 
Square free? 
and 
are 
, then 
, 
so that 
does not contain an odd edge-cut. 
Drupal
CSI of Charles University