On the impossibility of decomposing binary matroids

被引：1

作者：

Leichter, Marilena ^{[1
]}

Moseley, Benjamin ^{[2
]}

Pruhs, Kirk ^{[3
]}

机构：

[1] Tech Univ Munich, Dept Math, Munich, Germany

[2] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA USA

[3] Univ Pittsburgh, Comp Sci Dept, Pittsburgh, PA 15260 USA

来源：

OPERATIONS RESEARCH LETTERS | 2022年 / 50卷 / 05期

关键词：

Matroid; Matroid coloring; Matroid decomposition; Matroid intersection; PARTITION;

D O I：

10.1016/j.orl.2022.09.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We show that there exist k-colorable matroids that are not (b, c)-decomposable when b and c are constants. A matroid is (b, c)-decomposable, if its ground set of elements can be partitioned into sets X-1, X-2, ... , X-l with the following two properties. Each set Xi has size at most ck. Moreover, for all sets Y such that | Y boolean AND Xi| <= 1 it is the case that Y is b-colorable. A (b, c)-decomposition is a strict generalization of a partition decomposition and, thus, our result refutes a conjecture from [4]. (C) 2022 Elsevier B.V. All rights reserved.

引用

页码：623 / 625

页数：3

共 7 条

[1]

Abdolazimi D, 2021, Arxiv, DOI arXiv:2111.12436

[2] The intersection of a matroid and a simplicial complex [J].