Conjecture Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.
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.
In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.
Problem Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?
Conjecture Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .
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 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.
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 bridgelesscubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .
Problem Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?
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
of 
is the minimum number of crossings in all drawings of 
-dimensional (hyper)cube 
is the graph whose vertices are all binary sequences of length 
edges whose deletion destroys every odd cycle. 
so that every other vertex can be reached from 
the number of non-Hamiltonian 3-regular graphs of size 
, and similarly denote by 
the number of non-Hamiltonian 3-regular 1-connected graphs of size 
? 
is defined to be 
where 
is the number of faces of 
.
so that every convex 4-polytope has fatness at most 
of great circles on a sphere with no three circles meeting at a point. The arrangement graph of 
-colourable. 
then 
for every funcoid 
and atomic f.o. 
and 
on the source and destination of 
then 
for every funcoid 
, 
. 
-graph if it has a bipartition 
so that every vertex in 
has degree 
and every vertex in 
has degree 
. 
-vertex 
-minor-free graph has at most 
cliques? 
, there exists a Fibonacci number divisible by 
, 
does not divide 
where 
is the Legendre symbol. 
in the hypercube. 
has a Hamilton cycle. 
be a positive integer. We say that a graph 
is the maximal degree of a graph 
-colorable. 
of graphs is 
-bounded if there exists a function 
so that every 
satisfies 
. 
, the family of graphs with no induced subgraph isomorphic to 
of 
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?
, we write 
if 
satisfies 
. The problem of finding such an integer 
(with 
) is the Discrete Log Problem.
be an integer and let 
denote the least integer 
such that there exists a simple graph on 
(first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy? 
and 
and let 
be a surface. Is it true that every optimal drawing of 
Drupal
CSI of Charles University