Cooperative coloring of matroids

Abstract: Let

M_{1}, M_{2}, l d o t s, M_{k}

be a collection of matroids on the same ground set

E

. A coloring

c : E i g h t a r r o w 1, 2, l d o t s, k

is called emph{cooperative} if for every color

j

, the set of elements in color

j

is independent in

M_{j}

. We prove that such coloring always exists provided that every matroid

M_{j}

is itself

k

-colorable (the set

E

can be split into at most

k

independent sets of

M_{j}

). We derive this fact from a generalization of Seymour's list coloring theorem for matroids, which asserts that every

k

-colorable matroid is

k

-list colorable, too. We also point on some consequences for the game-theoretic variants of cooperative coloring of matroids.

This page was built for publication: Cooperative coloring of matroids