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 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.
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 ?
Conjecture The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1.
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 .
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .
2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.
The crossing number of is the minimum number of crossings in all drawings of in the plane.
The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.
Conjecture Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .
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
The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.
Question Is it true that for every (sub)cubic graph , we have ?
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 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 Suppose that is a -edge-critical graph. Suppose that for each edge of , there is a list of colors. Then is -edge-colorable unless all lists are equal to each other.
Conjecture There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .
A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.
Problem Is it true that for every , all but finitely many -regular graphs have friendly partitions?
login/create account
of edges such that every vertex is incident to exactly one edge from 
generators and exponent 
, is it necessarily finite? 
and 
has equivalence covering number 
. 
is a non-empty graph containing no induced odd cycle of length at least 
, then there is a 
-vertex colouring of 
, then 
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
?
-connected planar graph, then 
has a Hamilton cycle. 
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 
. ![$ p \in {\mathbb Q}[x] $](/files/tex/a72fcb0a006c3c2afb3ba69722ccdb2599b83e90.png)
rationally derived if all roots of 
and the nonzero derivatives of 
. 
-degenerate graph (a forest) and a 
, is the smallest integer 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
and for every vertex 
a non-negative integer 
which we think of as the amount of gold at 
. 
is a 
for all primes 
, where 
is prime. 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
of 
-dimensional (hyper)cube 
is the graph whose vertices are all binary sequences of length 
-balls?
is a graph, 
is admissable, and 
is even for every 
, then 
has a faithful cover. 
such that for any pair 
there are 
edge-disjoint paths from 
to 
(probably 
suffices) so that every embedded (loopless) graph with edge-width 
has a 5-local-tension. 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
of a graph 
-graph if it has a bipartition 
so that every vertex in 
has degree 
and every vertex in 
has degree 
. 
of a graph 
? 
be a graph. If 
are two integers, a 
-colouring of 
to 
such that 
for each edge 
. Given a list assignment 
of 
such that 
for every 
. A list assignment 
and 
for each vertex 
. Given such a list assignment 
, the graph 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
of 
of 
suffices) so that every graft with minimum 
. 
Drupal
CSI of Charles University