4-连通P₀-Minor-Free图的特征

A Characterization of 4-Connected Graphs with No P₀-Minor

摘要: 设H和G是两个图，如果图H可以通过从图G的一个子图中收缩边然后删除产生的环和平行边得到，我们就把图H叫做图G的一个minor。如果图G没有同构于图H的minor，我们称图G为H-minor-free图。图论中很多猜想都与H-minor-free图有关，例如Hadwiger猜想和Tutte 4-流猜想等。为了推动这些猜想的解决，我们目前非常关注Petersen-minor-free图的结构。由于它们都是15条边的3-连通图，直接刻画起来比较困难。因此为了刻画Petersen-minor-free图，许多学者尝试对每个边数小于15的3-连通图进行刻画去接近Petersen-minor-free图。记P₀为Petersen收缩两条完美匹配边和一条非完美匹配边得到的子图基础上添加一条边得到的13条边的图。本文下面将给出完整的4-连通P₀-minor-free图的刻画。

Abstract: For two given graphs H and G, if H can be obtained from a subgraph of G by contracting edges then deleting the resulting loops and parallel edges, we call H a minor of G. If G has no minor isomorphic to H, G is H-minor-free, and H is a forbidden minor of G. In graph theory, many important conjectures are related to H-minor-free graphs such as Hadwiger’s conjecture and Tutte’s 4-flow conjecture. To solve the above conjectures, we attempt to characterize Petersen-minor-free graphs. Let H is a graph with 15 edges. It is difficult to characterize H-minor-free graphs, thus to characterize Petersen-minor-free graphs, many scholars try to characterize every 3-connected graph with edges less than 15 to get close to Petersen graph. We denote the graph obtained by contracting two edges of a perfect matching of the Petersen, contracting one other edge and adding one edge. In this paper, we characterize 4-connected P₀-minor-free graphs.