Partitioning a matroid into independent sets
(suggested by Kristóf Bérczi, Csaba Király and Tamás Király)
Let be a matroid and be positive integers such that . Give a characterization of the existence of a partition of such that is an independent set for any subset of indeces.
What is known?
When is arbitrary and , the problem can be solved easily by using the matroid partition algorithm.
If , then it is not difficult to see that there exists a proper partition if and only if the matroid obtained by taking parallel copies of each element of can be partitioned into independent sets. Hence the first open case is when and .
For the graphic matroid of a graph , the problem asks for a coloring of the edges by colors in which each cycle receives at least different colors. That is, when then we are looking for a coloring of the edges by colors such that there is no two-colored cycle in . There are several results on so-called acyclic colorings of graphs, but in that case a proper coloring of the edges is needed not containing two-colored cycles.