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 is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.
An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .
Problem Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?
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 .
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 Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?
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 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 The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than
Problem Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?
Conjecture If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.
login/create account
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 
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 
, then there is a 
-vertex colouring of 
-norm of a path partition on a directed graph 
is no more than the maximal size of an induced 
for principal funcoid 
and a set 
of funcoids of appropriate sources and destinations. 
is for every sets 
and 
:
in the 
-dimensional hypercube? 
be an elliptic curve over a number field 
. Then the order of the zeros of its 
, at 
is the Mordell-Weil rank of 
. 
-factor in a graph 
contains and 
are simple finite graphs, then 
. 
is the 
with 
so that the 
has no clique or independent set of size 
. 
. 
has distinct subset sums if distinct subsets of 
whenever 
has distinct subset sums. 
. 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
of graphs and an integer 
of 
such that there exists a graph on 
such that 
.
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
, there is an integer 
so that every strongly 
and 
. It is equivalent to a homomorphism of the digraph onto some tournament of order 
if 
if 
. Assume we start with some number 
. 
-regular graph, where 
, then 
of a graph 
of 
edges whose deletion destroys every triangle. 
where 
for 
? 
let 
denote the minimal number 
such that there is a rainbow 
in every equinumerous 
for every 
, 
. 
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
Drupal
CSI of Charles University