Rainbow and monochromatic circuits and cuts in binary matroids
Rainbow and monochromatic circuits and cuts in binary matroids
复制标题
彩虹和单色电路以及二元拟阵中的切割
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Tamás Schwarcz
中科院分区：
文献类型：
--
作者：
Kristóf Bérczi;Tamás Schwarcz
给定一个拟阵及其基集的一个着色，如果它的元素中没有两个元素具有相同的颜色，则它的元素的子集称为彩虹色。我们证明，如果一个二元拟阵的秩$r$是着色与确切的$r$的颜色，那么$M$要么包含一个彩虹色的电路或单色切割。由于这类二元拟阵在取M下是封闭的，这直接意味着$M$要么包含彩虹色切割，要么也包含单色回路。作为一个副产品，我们给出了一个特征的二进制拟阵方面的减少分区拟阵。受B\'erczi等人的猜想启发，本文还分析了二元拟阵的覆盖数与其任意彩虹无圈着色中的最大色数或色类的最大尺寸之间的关系。对于简单的图拟阵，我们证明了只有当图是$（2，3）$-稀疏的，即它在$2$-维刚性拟阵中是独立的，才存在一个彩虹无圈着色，它最多使用每种颜色两次。此外，我们给出了一个完整的刻画极小刚性图允许这样的染色。
Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if a binary matroid of rank $r$ is colored with exactly $r$ colors, then $M$ either contains a rainbow colored circuit or a monochromatic cut. As the class of binary matroids is closed under taking duals, this immediately implies that $M$ either contains a rainbow colored cut or a monochromatic circuit as well. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids. Motivated by a conjecture of B\'erczi et al., we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the $2$-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.
影响因子：
1.1
作者：
Im, Sungjin;Moseley, Benjamin;Pruhs, Kirk
通讯作者：
Pruhs, Kirk