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.