Conjecture Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .
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 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 .
Conjecture It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?
Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?
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 simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.
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?
Conjecture Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.
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?
Conjecture If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .
Conjecture If is a bridgelesscubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .
We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.
Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.
Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?
Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?
Problem (2) Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .
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.
Conjecture For every graph without a bridge, there is a flow .
Conjecture There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.
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.
Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .
Conjecture For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.
Problem Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.
login/create account
be an eulerian graph of minimum degree 
, and let 
be an eulerian tour of 
, whether there exists a homomorphism from 
for some constant 
? 
-connected finite graph, is there an assignment of lengths 
to the edges of 
-geodesic cycle is 
has distinct subset sums if distinct subsets of 
have distinct sums.
whenever 
has distinct subset sums. 
) Find a sufficient condition for a straight 
) Let 
be a simple regular ordered 
-stage graph. Suppose that the graph 
is externally connected, for some 
. Then the graph 
is rearrangeable. 
suffices) so that every graft with minimum 
-cut size at least 
contains a 
. 
is the only 
-chromatic double-critical graph 
, 
be a positive integer. We say that a graph 
is the maximal degree of a graph 
-colorable. 
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 
-
points is contained in at most 
-edge-coloring so that any two edges which share 
? 
, 
so that 
does not contain an odd edge-cut. 
vertices, then 
. 
suffices) so that every embedded (loopless) graph with edge-width 
has a 5-local-tension. 
be an indexed family of sets.
for 
.
on the lattice 
of all finite unions of products.
a bijection from hyperfuncoids 
defining the inverse bijection? If not, characterize the image of the function 
of complements of elements of the set 
is 2-large, then 
. 
.
be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than 
-hardness? 
cycles. 
entries by 
) so that the resulting matrix has all eigenvalues of magnitude at most 
. 
of 
and its first arbitrary shortest spanning tree 
. We define the next graph 
and find on 
the second arbitrary shortest spanning tree 
. We continue similarly by finding 
on 
, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let 
be the graph obtained as union of all 
containing a Hamiltonian path.
or 
which divides both 
(see 
(see 
be a sequence of nonnegative integers which strictly decreases until 
.
with 
crossings, but not with less crossings. 
the following inequality holds 
.
so that antipodal points of 
receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero. 
paths. 
into 
so that the graph induced by 
is acyclic for 
. 
such that 
meets 
in at most one vertex, 
. 
is called a Diophantine 
-tuple if 
is a perfect square for all 
. 
is a Diophantine quadruple and 
, then 
of 
is the graph whose vertices are all binary sequences of length 
in 
there is an integer 
such that 
or prove that such integers do not exist. 
Frege system 
but requires exponential size 
proofs. 
such that for every graph ![\[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\]](/files/tex/989db06683633e86605c26e7d9f0bffc7e46a496.png)
Drupal
CSI of Charles University