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 .
A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
Begin with the generating function for unrestricted partitions:
(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...
Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.
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.
For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).
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 .
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?
If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .
Problem Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?
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.
Question What is the Waring rank of the determinant of a generic matrix?
For simplicity say we work over the complex numbers. The generic matrix is the matrix with entries for . Its determinant is a homogeneous form of degree , in variables. If is a homogeneous form of degree , a power sum expression for is an expression of the form , the (homogeneous) linear forms. The Waring rank of is the least number of terms in any power sum expression for . For example, the expression means that has Waring rank (it can't be less than , as ).
The generic determinant (or ) has Waring rank . The Waring rank of the generic determinant is at least and no more than , see for instance Lower bound for ranks of invariant forms, Example 4.1. The Waring rank of the permanent is also of interest. The comparison between the determinant and permanent is potentially relevant to Valiant's "VP versus VNP" problem.
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.
Conjecture Let be a graph and be a positive integer. The power of , denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also subdivision of , denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have . Now we can define the fractional power of a graph as follows: Let be a graph and . The graph is defined by the power of the subdivision of . In other words . Conjecture. Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have . In [1], it was shown that this conjecture is true in some special cases.
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 If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .
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.
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,
Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.
login/create account
and 
are 
-vertex graphs and 
, then 
be a graph and let 
such that for any pair 
there are 
edge-disjoint paths from 
to 
in 
edge-disjoint trees, each of which contains 
. 
-flow 
on 
of 
from the edge set of 
, for all 
, and 
. The circular flow number of 
has a nowhere-zero 
, and it is denoted by 
.
be an integer and 
-regular graph. If 
. 
of co-prime positive integers 
for 
. 
vertices. 
for every endo-
? 
which is slice, is it a ribbon knot?
and every positive integer 
so that every simple 
has a 
with 
. 
, then 
denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let 
denote the cardinality of a minimum feedback vertex set (set of vertices 
so that 
is acyclic). 
. 
so that every abelian group 
with 
so that the 
has no clique or independent set of size 
. 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
. 
be an elliptic curve over a number field 
. Then the order of the zeros of its 
-function, 
, at 
is the Mordell-Weil rank of 
. 
arc-disjoint transitive subtournaments of order 3. 
are prime.
is called cycle-continuous if the pre-image of every element of the (binary) cycle space of 
so that there is no cycle continuous mapping between 
and 
whenever 
? 
there is a sequence of tautologies of depth 
Frege system 
but requires exponential size 
proofs. 
generic matrix? 
for 
. Its determinant is a homogeneous form of degree 
variables. If 
is a homogeneous form of degree 
, the 
(homogeneous) linear forms. The Waring rank of 
means that 
has Waring rank 
(it can't be less than 
).
generic determinant 
(or 
) has Waring rank 
. The Waring rank of the 
generic determinant is at least 
and no more than 
, see for instance 
.
, the union of any 
-degenerate graph. 
points is contained in at most 
-edge-coloring so that any two edges which share 
power of 
, is defined on the vertex set 
, by connecting any two distinct vertices 
and 
with distance at most 
. Also 
, is constructed by replacing each edge 
of 
, we have 
.
. The graph 
is defined by the 
power of the 
subdivision of 
.
and 
be a positive integer greater than 1. Then for any positive integer 
, we have 
.
is the maximal degree of a graph 
-colorable. 
people admits a solution is 
. 
.
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. 
-connected planar graph, then 
has a Hamilton cycle. 
? 
always rational? 
is an assignment of colors to the vertices and the edges of 
, equals the minimum number of colors needed in a total coloring of ![\[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]](/files/tex/d4ea30e930ec20e02c5a03c6322e6d99a6bdb63a.png)
and 
are 
-
are simple finite graphs, then 
. 
is the 
Drupal
CSI of Charles University