On partitioning two matroids into common independent subsets |
| |
Authors: | Daniel Kotlar Ran Ziv |
| |
Institution: | Computer Science Department, Tel-Hai Academic College, Upper Galilee 12210, Israel |
| |
Abstract: | Let M1 and M2 be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A1,A2,…,Ak+1 of S, such that ispM1(Ai)≠Ø, and similarly for M2, then S is partitioned into k sets, each independent in both M1 and M2. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota. |
| |
Keywords: | Matroid Common partition Rota's conjecture |
本文献已被 ScienceDirect 等数据库收录! |
|