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?
Conjecture For all positive integers and , there exists an integer such that every graph of average degree at least contains a subgraph of average degree at least and girth greater than .
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?
Conjecture A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in -outerplanar graphs or tree-width graphs?
Conjecture For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?
Conjecture Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.
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 .
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.
Conjecture Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.
Proposition It is easy to prove that is the infinitely small right neighborhood filter of point .
If proved true, the conjecture then can be generalized to a wider class of posets.
login/create account
, all but finitely many 
, every (loopless) graph 
with 
immerses 
. 
has an acyclic induced subdigraph of order at least 
. 
-manifold, then 
and 
, there exists an integer 
such that every graph of average degree at least 
which is slice, is it a ribbon knot?
. The graph 
is defined to be the 
-power of the 
.
. Then 
. 
edges whose deletion destroys every odd cycle. 
-connected cubic planar graph can be decomposed into two Hamilton cycles. 
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
. 
, is the graph with vertex set 
and two points adjacent if the distance between them is an odd integer. 
? 
, it is impossible to cover a square of side greater than 
unit squares. ![\[ F_n = 2^{2^n } + 1 \]](/files/tex/0da5a50010e4e5df91c0d58080245ece34ec9ca6.png)
that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.
and graph 
. ![$ p \in [0,1] $](/files/tex/1d076f7332523eb59bd7deae19667f83f0a3b6e0.png)
, we let 
denote a subgraph of 
.
so that 
? 
and every positive integer 
so that every simple 
has a 
. 
there is an integer 
such that every set of at least 
collinear points or an empty hexagon. 
. Suppose that 
and each vertex of 
vertices of 
, and let 
be an eulerian tour of 
, for 
if each of the color classes is of size of either 
or 
? 
be an integer and let 
. Then either 
minor for some 
or 
be the complete funcoid corresponding to the usual topology on extended real line ![$ [-\infty,+\infty] = \mathbb{R}\cup\{-\infty,+\infty\} $](/files/tex/3252019c60a83f00ff396d823dbff8040639f409.png)
. Let 
be the order on this set. Then 
is a complete funcoid. 
is the infinitely small right neighborhood filter of point ![$ x\in[-\infty,+\infty] $](/files/tex/4e57a21194d8d5a659e259a111ed13a9c23b52a1.png)
. 
which cannot be expressed as a union of 
triangle free graphs? 
Drupal
CSI of Charles University