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,
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 ?
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 There exists an integer such that every -arc-strong digraph with specified vertices and contains an out-branching rooted at and an in-branching rooted at which are arc-disjoint.
Conjecture If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .
Conjecture For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.
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.
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 For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive 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 Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .
Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .
There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .
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.
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
Conjecture Let be an -uniform-partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
login/create account
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 
plus one or two. In other words, ![\[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]](/files/tex/d4ea30e930ec20e02c5a03c6322e6d99a6bdb63a.png)
-connected cubic planar graph can be decomposed into two Hamilton cycles. 
is 2-large, then 
-minor-free graph is 
-list-colourable for some constant 
. 
such that every planar graph has obstacle number at most 
where 
is the number of vertices. What is the distribution of 
for 
? 
of graphs and an integer 
, the Turán number 
of 
such that there exists a graph on 
such that 
.
be a digraph all of whose strong components are nontrivial. Then 
. 
for 
. 
and 
let 
denote the minimal number 
such that there is a rainbow 
in every equinumerous 
-coloring of 
for every 
, 
. 
is a finite field with at least 4 elements and 
matrix with entries in 
which have no coordinates equal to zero such that 
. 
in the hypercube. 
so that every polytope of dimension 
has a 
, then there is a 
-vertex colouring of 
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 
. 
such that every digraph of minimum outdegree at least 
if 
if 
. Assume we start with some number 
of the current number. Prove that no matter what the initial number is we eventually reach 
. 
in 
, let the symmetry group of 
ie: isotopy classes of diffeomorphisms of 
of 
is the unlink. Let 
be the subgroup of 
consisting of diffeomorphisms of 
given by restricting the diffeomorphism to the 
is a signed symmetric group -- the wreath product of a symmetric group with 
. 
be an abelian group. Is the 
such that every 
cliques? 
for every endo-
, let 
be the statement that given any exact 
, 
, or 
. 
is a tournament of order 
arc-disjoint transitive subtournaments of order 3. 
and 
are 
, then 
vertices. 
is arbitrarily large? 
rectangular 
inside an 
? 
be an 
-
is the maximum number of pairwise disjoint edges in 
is the size of the smallest set of vertices which meets every edge, then 
. 
is a prime iff 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
-colored countably infinite complete subgraph. Then 
, 
, or 
.
always rational? 
and every positive integer 
so that every simple 
has a 
. 
Drupal
CSI of Charles University