Matroid colorings can differ for lists versus simple sets

A note on the list chromatic number of two matroids

Discrete Mathematics

Summary

When trying to color objects so that certain groupings don’t share colors, two special combinatorial structures called matroids are studied. The authors show that the minimum number of colors needed when each element has its own color list can be larger than when colors are chosen freely. They give an example where two matroids require only two colors generally but need three when restricted to lists, solving a previously open question. They also prove that under certain conditions, two matroids each colorable with two colors are still colorable with two colors even when lists are assigned.

What this means in practice

  • For network schedulers: Determine minimum coloring restrictions for resource and channel assignment when constraints differ per element in network scheduling.
  • For circuit designers: Understand color assignment constraints in circuit components modeled by matroids to avoid conflicts under list-based restrictions.

A theory result. No direct application yet.

Authors

Bence Garami

Abstract

We study list coloring of common independent sets of two matroids. We construct a graphic matroid $M_1$ and a partition matroid $M_2$ with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Király, later stated as a conjecture by Aharoni, Berger, Guo, and Kotlar. We also show that if two strongly base-orderable matroids are each $2$-colorable, then their intersection is $2$-list-colorable.