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 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.
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 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 Let and . Then for any neighborhood there is such that is periodic point of
There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for
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.
login/create account
is a graph, we say that a partition of 
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. 
. The chromatic number of its square is
if 
, \item at most 
if 
, \item at most 
if 
. 
-norm of a path partition on a directed graph 
is no more than the maximal size of an induced 
denote the 
satisfies 
. 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
vertices can be decomposed into at most 
cycles. 
is a tournament of order 
arc-disjoint transitive subtournaments of order 3. 
, all but finitely many 
be the unique integer (with respect to a fixed 
) such that
is a prime iff ![$$ \displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor $$](/files/tex/99af565f4cc4d3bab11eb3fbf54f78626678d484.png)
has a homomorphism to 
. 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
and 
. Then for any neighborhood 
there is 
such that 
is periodic point of 
vector fields . In the case of diffeos this was proved by Charles Pugh for 
. In the case of Flows this has been solved by Sushei Hayahshy for 
is not greater than 
, what is the smallest integer 
such that 
? ![\[ 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.
Drupal
CSI of Charles University