Small separations in pinch-graphic matroids
成果类型：
Article
署名作者：
Guenin, Bertrand; Heo, Cheolwon
署名单位：
University of Waterloo; Korea Institute for Advanced Study (KIAS)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-01950-8
发表日期：
2024
页码：
81-111
关键词：
摘要：
Even-cycle matroids are elementary lifts of graphic matroids. Pinch-graphic matroids are even-cycle matroids that are also elementary projections of graphic matroids. In this paper we analyze the structure of 1-, 2-, and 3-separations in these matroids. As a corollary we obtain a polynomial-time algorithm that reduces the problem of recognizing pinch-graphic matroids to internally 4-connected matroids. Combining this with earlier results (Guenin and Heo in Recognizing even-cycle and even-cut matroids manuscript, 2020; Guenin and Heo in Recognizing pinch-graphic matroids manuscript, 2020) we obtain a polynomial-time algorithm for recognizing even-cycle matroids and we obtain a polynomial-time algorithm for recognizing even-cut matroids.
来源URL：