List coloring of two matroids through reduction to partition matroids

DOI10.1137/20M1385615MaRDI QIDQ5157385zbMATH OpenOpenAlexFDO

Authors Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi

Publication date 18 October 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.10485

zbMATH Keywords

list coloringmatroidspacking common basesweak maps

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Abstract: In the list coloring problem for two matroids, we are given matroids $M_1=(S,{calI}_1)$ and $M_2=(S,{calI}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that given arbitrary lists $L_s$ of $k$ colors for $sinS$, it is possible to choose a color from each list so that every monochromatic set is independent in both $M_1$ and $M_2$. When both $M_1$ and $M_2$ are partition matroids, Galvin's list coloring theorem for bipartite graphs gives the answer. One of the main open questions is to decide if there exists a constant $c$ such that if the coloring number is $k$ (i.e., the ground set can be partitioned into $k$ common independent sets), then the list coloring number is at most $ccdotk$. We consider matroid classes that appear naturally in combinatorial optimization problems, namely graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much, and might be of independent combinatorial interest. In particular, we show that if $M=(S,calI)$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,calJ)$ with $calJsubseteqcalI$ in which $S$ can be partitioned into (A) $k$ independent sets if $M$ is a transversal matroid, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $lceilkr/(r-1)ceil$ independent sets if $M$ is a paving matroid of rank $r$, and (D) $2k-2$ independent sets if $M$ is a gammoid. We extend our results by showing that the existence of a matroid $N$ with $chi(N)leq2chi(M)$ implies the existence of a matroid $N^{\prime }$ with $chi(N^{\prime })leq2chi(M^{\prime })$ for every truncation $M^{\prime }$ of $M$.

Recommendations

• List coloring of matroids and base exchange properties
• Coloring by two-way independent sets
• On-line list coloring of matroids
• On partitioning two matroids into common independent subsets
• The coloring game on matroids

Cites work

• A Catalogue of Combinatorial Geometries
• A generalization of Kónig's theorem
• A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
• A note on list arboricity
• Connections in combinatorial optimization
• Decomposition of Finite Graphs Into Forests
• Disjoint Common Transversals and Exchange Structures
• Gammoids and transversal matroids
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 3342868 (Why is no real title available?)
• Lattice Theory of Generalized Partitions
• List coloring of matroids and base exchange properties
• On the Abstract Properties of Linear Dependence
• On the asymptotic proportion of connected matroids
• On the number of matroids compared to the number of sparse paving matroids
• Properties of rank preserving weak maps
• The intersection of a matroid and a simplicial complex
• The list chromatic index of a bipartite multigraph
• The matroid intersection cover problem
• Transversals and matroid partition
• Weak Maps of Combinatorial Geometries

Cited in

(8)

• Coloring by two-way independent sets
• On the impossibility of decomposing binary matroids
• Rainbow and monochromatic circuits and cocircuits in binary matroids
• List coloring of matroids and base exchange properties
• On-line list coloring of matroids
• Choice functions
• Partitioning into common independent sets via relaxing strongly base orderability
• Efficiently coloring the intersection of a general matroid and combinatorial matroids

This page was built for publication: List coloring of two matroids through reduction to partition matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5157385)