Branch-width and well-quasi-ordering in matroids and graphs

被引：64
|
作者：
Geelen, JF [1 ]
Gerards, AMH
Whittle, G
机构：
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[2] CWI, NL-1090 GB Amsterdam, Netherlands
[3] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
[4] Univ Victoria, Sch Math & Comp Sci, Wellington, New Zealand
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2002年 / 84卷 / 02期
基金：
加拿大自然科学与工程研究理事会;
关键词：
matroids; graphs; minors; finite fields; connectivity; submodularity; branch-width; tree-width; well-quasi-ordering;
D O I：
10.1006/jctb.2001.2082
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We prove that a class of matroids representable over a fixed finite field and with bounded branch-width is well-quasi-ordered under taking minors. With some extra work. the result implies Robertson and Seymour's result that graphs with bounded tree-width (or equivalently, bounded branch-width) are well-quasi-ordered under taking minors. We will not only derive their result from our result on matroids, but we will also use the main tools for a direct proof that graphs with bounded branch-width are well-quasi-ordered under taking minors. This proof also provides a model for the proof of the result on matroids, with all specific matroid technicalities stripped off. (C) 2002 Elsevier Science (USA).
引用
收藏
页码：270 / 290
页数：21
相关论文
共 40 条
  • [21] Dominating sets in planar graphs: Branch-width and exponential speed-up
    Fomin, FV
    Thilikos, DM
    PROCEEDINGS OF THE FOURTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2003, : 168 - 177
  • [22] Integer packing sets form a well-quasi-ordering
    Del Pia, Alberto
    Gijswijt, Dion
    Linderoth, Jeff
    Zhu, Haoran
    OPERATIONS RESEARCH LETTERS, 2021, 49 (02) : 226 - 230
  • [23] Dominating sets in planar graphs: Branch-width and exponential speed-up
    Fomin, Fedor V.
    Thilikos, Dimitrios M.
    SIAM JOURNAL ON COMPUTING, 2006, 36 (02) : 281 - 309
  • [24] Strong immersion is a well-quasi-ordering for semicomplete digraphs
    Barbero, Florian
    Paul, Christophe
    Pilipczuk, Michal
    JOURNAL OF GRAPH THEORY, 2019, 90 (04) : 484 - 496
  • [25] Approximating clique-width and branch-width
    Oum, Sang-il
    Seymour, Paul
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 514 - 528
  • [26] Two forbidden induced subgraphs and well-quasi-ordering
    Korpelainen, Nicholas
    Lozin, Vadim
    DISCRETE MATHEMATICS, 2011, 311 (16) : 1813 - 1822
  • [27] Rank-width is less than or equal to branch-width
    Oum, Sang-il
    JOURNAL OF GRAPH THEORY, 2008, 57 (03) : 239 - 244
  • [28] Satisfiability, Branch-Width and Tseitin tautologies
    Michael Alekhnovich
    Alexander Razborov
    computational complexity, 2011, 20 : 649 - 678
  • [29] A parametrized algorithm for matroid branch-width
    Hlineny, P
    SIAM JOURNAL ON COMPUTING, 2005, 35 (02) : 259 - 277
  • [30] SATISFIABILITY, BRANCH-WIDTH AND TSEITIN TAUTOLOGIES
    Alekhnovich, Michael
    Razborov, Alexander
    COMPUTATIONAL COMPLEXITY, 2011, 20 (04) : 649 - 678
1234