List colouring of two matroids through reduction to partition matroids
List colouring of two matroids through reduction to partition matroids
复制标题
通过简化分区拟阵来列出两个拟阵的着色
DOI：
--
复制
发表时间：
2019
影响因子：
0.8
通讯作者：
Y. Yamaguchi
中科院分区：
文献类型：
--
作者：
Kristóf Bérczi;Tamás Schwarcz;Y. Yamaguchi
在两个拟阵的列表着色问题中，我们给出拟阵$M_1=（S，\mathcal{I}_1）$和$M_2=（S，\mathcal{I}_2）$在相同的基集$S$上，目标是确定最小的数$k$，使得给定任意列表$L_s$的$k$颜色，可以从每个列表中选择一种颜色，使得每个单色集合在$M_1$和$M_2$中是独立。当$M_1$和$M_2$都是划分拟阵时，Galvin著名的二部图列表着色定理给出了答案。其中一个主要的开放问题是决定是否存在一个常数$c$，使得如果着色数是$k$（即，基集可以被划分为$k$个独立集），则列表着色数至多为$c\cdot k$。在本文中，我们考虑拟阵类，自然出现在组合和图形优化问题，即图形拟阵，铺路拟阵和gammoids。我们表明，如果这两个拟阵是从这些基本类，然后列表着色数是最多两倍的着色数。
证明是基于一种新的方法，减少一个拟阵的分区拟阵，并可能是独立的组合利益。特别是，我们证明，如果$M=（S，\mathcal{I}）$是一个拟阵，其中$S$可被划分为$k$个独立集，则存在一个划分拟阵$N=（S，\mathcal{J}）$有$\mathcal{J}\subseteq\mathcal{I}$其中$S$可以被划分成（A）$\lceil kr/（r-1）\rceil$独立集如果$M$是秩$r$的铺路拟阵，（B）M是图拟阵时的2k-1独立集，（C）M是横截拟阵时的k独立集，（D）M是gammoid时的2k-2独立集。我们还展示了如何减少技术可以扩展到强基有序拟阵，可能作为一个有用的工具，在有关的问题包装基地的两个拟阵。
In the list colouring problem for two matroids, we are given matroids $M_1=(S,\mathcal{I}_1)$ and $M_2=(S,\mathcal{I}_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$ colours for $s\in S$, it is possible to choose a colour 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 celebrated list colouring 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 colouring number is $k$ (i.e., the ground set can be partitioned into $k$ independent sets), then the list colouring number is at most $c\cdot k$. In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, namely graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list colouring number is at most twice the colouring number.
The proof is based on a novel approach that reduces a matroid to a partition matroid, and might be of independent combinatorial interest. In particular, we show that if $M=(S,\mathcal{I})$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,\mathcal{J})$ with $\mathcal{J}\subseteq\mathcal{I}$ in which $S$ can be partitioned into (A) $\lceil kr/(r-1)\rceil$ independent sets if $M$ is a paving matroid of rank $r$, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $k$ independent sets if $M$ is a transversal matroid, and (D) $2k-2$ independent sets if $M$ is a gammoid. We also show how the reduction technique can be extended to strongly base orderable matroids that might serve as a useful tool in problems related to packing bases of two matroids.
影响因子：
1.1
作者：
Im, Sungjin;Moseley, Benjamin;Pruhs, Kirk
通讯作者：
Pruhs, Kirk