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.
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 ?
For every finite multiplicative group , let () denote the smallest integer so that every sequence of elements of has a subsequence of length (length ) which has product equal to 1 in some order.
Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .
Problem () Find a sufficient condition for a sequence of partitions of to be complete, i.e. such that the product of their stabilizers is equal to the whole symmetric group on . In particular, what about completeness of the sequence , given a partition of and a permutation of ?
Conjecture (Beneš) Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then
For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.
Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?
Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.
Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?
2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?
3. Finally, what could one say about higher dimensional analogs of this question?
Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n
Conjecture Given any complex numbers which are linearly independent over the rational numbers , then the extension field has transcendence degree of at least over .
Question Can either of the following be expressed in fixed-point logic plus counting: \item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?
Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?
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).
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 ?
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 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?
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 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.
login/create account
always rational? 
be a positive integer. We say that a graph 
is strongly 
is the maximal degree of a graph 
-colorable. 
has a homomorphism to 
. 
with minimum outdegree at least 
denote the graph with vertex set consisting of all lines through the origin in 
and two vertices adjacent in 
? 
are invertible 
matrices with entries in 
for a prime 
, then there is a 
submatrix 
of ![$ [B_1 B_2 \ldots B_p] $](/files/tex/86661dc2948aeca789b4392c2e2a9cbf7d96f735.png)
so that 
and 
has equivalence covering number 
. 
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 
(
) denote the smallest integer 
so that every sequence of 
(length 
) which has product equal to 1 in some order. 
for every finite group 
be the flow polynomial of a graph 
equals the number of 
for every 2-edge-connected graph 
be a non-empty finite set. Given a partition 
of 
, is the group formed by all permutations of 
.
) Find a sufficient condition for a sequence of partitions 
of 
is equal to the whole symmetric group 
on 
, given a partition 
of 
be a uniform partition of 
be a permutation of 
. Suppose that the set 
is transitive, for some integer 
. Then 
so that every sequence of elements of 
has a nontrivial subsequence which sums to zero.
? 
which are linearly independent over the rational numbers 
, then the extension field 
has transcendence degree of at least 
and 
are 
of edges such that every vertex is incident to exactly one edge from 
for some filter objects 
, 
. Particularly, is this formula true for 
? 
for some filter objects 
grid. The first player (if any) to occupy a set of 
.
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). 
. 
are graphs, a function 
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 
? 
and 
so that every other vertex can be reached from 
Drupal
CSI of Charles University