TOPICS
Search

Matroid Coloring


A matroid coloring assigns colors to the elements of the finite ground set of a loopless matroid so that every color class is independent. Its chromatic number is the least possible number of colors. For two loopless matroids on the same finite ground set, a common coloring requires each color class to be independent in both matroids.

In list coloring, each element e must receive a color from its prescribed list L(e). The common list chromatic number chi_l(M_1,M_2) is the least k for which every assignment of lists of size k permits a common coloring (Garami 2026).

Garami (2026) constructed a graphic matroid M_1 and a partition matroid M_2 with

 chi(M_1,M_2)=2, chi_l(M_1,M_2)=3.

Thus equality of the chromatic and list chromatic numbers for one matroid does not extend to pairs of matroids. Garami (2026) also proved that two strongly base-orderable matroids, each admitting a coloring with two colors, have common list chromatic number at most 2.


See also

Graphic Matroid, Matroid, Matroid Intersection, Partition Matroid, Strongly Base-Orderable Matroid

Explore with Wolfram|Alpha

References

Garami, B. "A Note on the List Chromatic Number of Two Matroids." 5 Oct 2026. https://arxiv.org/abs/2610.07318.

Cite this as:

Weisstein, Eric W. "Matroid Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MatroidColoring.html

Subject classifications