solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看96次
A short derivation of the structure theorem for graphs with excluded topological minors. (arXiv:1807.01119v1 [math.CO])
来源于:arXiv
As a major step in their proof of Wagner's conjecture, Robertson and Seymour
showed that every graph not containing a fixed graph $H$ as a minor has a
tree-decomposition in which each torso is almost embeddable in a surface of
bounded genus. Recently, Grohe and Marx proved a similar result for graphs not
containing $H$ as a topological minor. They showed that every graph which does
not contain $H$ as a topological minor has a tree-decomposition in which every
torso is either almost embeddable in a surface of bounded genus, or has a
bounded number of vertices of high degree. We give a short proof of the theorem
of Grohe and Marx, improving their bounds on a number of the parameters
involved. 查看全文>>