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 An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.
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 ?
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 .
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 .
Problem Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?
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 .
Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.
Conjecture Every arrangement graph of a set of great circles is -colourable.
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 Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?
login/create account
or 
which divides both 
(see 
(see 
. 
. 
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.
? 
be an abelian group. Is the 
cycles. 
such that for any pair 
there are 
edge-disjoint paths from 
to 
in 
edge-disjoint trees, each of which contains 
. 
. 
be positive semidefinite, by Jensen's inequality, it is easy to see ![$ [tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}} $](/files/tex/f5fa90ccf8c1dde9b9bf1f21399b3b5428dab81d.png)
, whenever 
.
, is it still valid?
, whether there exists a homomorphism from 
for some constant 
? 
such that 
or prove that such integers do not exist. 
is the adjacency matrix of a 
-regular graph, then there is a symmetric signing of 
entries by 
) so that the resulting matrix has all eigenvalues of magnitude at most 
. 
denote the 
? 
in the hypercube. 
such that the vertices of any digraph with minimum outdegree 
-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 
. 
such that every graph with average degree smaller than 
of great circles on a sphere with no three circles meeting at a point. The arrangement graph of 
-colourable. 
, 
directed paths. 
and 
are 
suffices) so that every graft with minimum 
. 
arc-disjoint directed cycles. 
for every 
with odd size.
for every 
. 
and 
and let 
be a surface. Is it true that every optimal drawing of 
can be represented as the sum of an odd prime number and an odd 
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