Some Recent Progress and Applications in Graph Minor Theory

被引：0
作者：
Ken-ichi Kawarabayashi
Bojan Mohar
机构：
[1] The National Institute of Informatics,Department of Mathematics
[2] Simon Fraser University,undefined
来源：
Graphs and Combinatorics | 2007年 / 23卷
关键词：
Graph minor theory; Tree-width; Tree-decomposition; Path-decomposition; Complete graph minor; Excluded minor; Complete bipartite minor; Connectivity; Hadwiger Conjecture; Grid minor; Vortex structure; Near embedding; Graphs on surfaces;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough'' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed.
引用
收藏
页码：1 / 46
页数：45
相关论文
共 241 条
[11]  
Böhme T.(1969)The point-arboricity of planar graphs J. London Math. Soc. 44 612-616
[12]  
Kostochka A.(1971)Graphs with forbidden subgraphs J. Combin. Theory 10 12-41
[13]  
Disjoint K(1996)Parallel complexity of partitioning a planar graph into vertex-induced forests Discrete Appl. Math. 69 183-198
[14]  
Bollobás B.(2000)Efficient algorithms for acyclic coloring graphs Theor. Comp. Sci. 230 79-95
[15]  
Thomason A.(2005)Graph minors and linkage problem I J. Graph Theory 49 75-91
[16]  
Bollobás B.(1983)Knots and links in spatial graphs J. Graph Theory 7 445-453
[17]  
Thomason A.(2005)Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs J. ACM 52 1-29
[18]  
Brunet R.(2004)Excluding any graph as a minor allows a low tree-width 2-coloring J. Combin. Theory Ser. B 91 25-41
[19]  
Mohar B.(2005)Coloring-flow duality of embedded graphs Trans. Amer. Math. Soc. 357 3993-4016
[20]  
Richter R.B.(1994)The depth-first search tree structure of T -free graphs J. Combin. Theory Ser. B 61 260-262
12345678910