List Coloring of Two Matroids through Reduction to Partition Matroids
List Coloring of Two Matroids through Reduction to Partition Matroids
复制标题
通过简化分区矩阵对两个拟阵进行列表着色
DOI：
10.1137/20m1385615
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Yutaro Yamaguchi
中科院分区：
文献类型：
--
作者：
Kristof Berczi;Tamas Schwarcz;Yutaro Yamaguchi
在两个拟阵的列表着色问题中，我们给定拟阵和在同一个基集上，目标是确定最小的数目，使得给定任意的颜色列表，可以从每个列表中选择一种颜色，使得每个单色集都是独立的。当和都是划分拟阵时，Galvin著名的二部图列表着色定理给出了答案。然而，对一般情况知之甚少。一个主要的开放问题是决定是否存在一个常数，使得如果色数是（即，基集可划分为公共独立集），则列表色数至多为。在本文中，我们考虑拟阵类，自然出现在组合和图形优化问题，特别是图形拟阵，铺路拟阵和gammoids。我们表明，如果这两个拟阵是从这些基本类，然后列表着色数是最多两倍的着色数。证明是基于一种新的方法，减少了拟阵的分区拟阵，而不会增加其着色数太多，可能是独立的组合利益。特别地，我们证明了如果是一个拟阵，其中可被划分为独立集，则存在一个划分拟阵，其中可被划分为（A）独立集，如果是一个横截拟阵，（B）独立集，如果是一个图拟阵，（C）独立集，如果是一个秩的铺路拟阵，（D）独立集，如果是一个gammoid.应该强调的是，在情况（A）、（B）和（D）中，的秩与的秩相同。我们进一步将我们的结果扩展到更广泛的家族，表明从这些类中取直和、同态像或截短拟阵会导致拟阵允许还原为色数最多为原始拟阵的两倍的划分拟阵。
In the list coloring problem for two matroids, we are given matroidsandon the same ground set, and the goal is to determine the smallest numbersuch that, given arbitrary listsofcolors for, it is possible to choose a color from each list so that every monochromatic set is independent in bothand. When bothandare partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constantsuch that if the coloring number is(i.e., the ground set can be partitioned intocommon independent sets), then the list coloring number is at most. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically 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 ifis a matroid in whichcan be partitioned intoindependent sets, then there exists a partition matroidwithin whichcan be partitioned into (A)independent sets ifis a transversal matroid, (B)independent sets ifis a graphic matroid, (C)independent sets ifis a paving matroid of rank, and (D)independent sets ifis a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank ofis the same as that of. We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.