论文标题
高度不可破坏的图形和固定的未成年人几乎是刚性的
Highly unbreakable graph with a fixed excluded minor are almost rigid
论文作者
论文摘要
图$ g $中的$ x \ subseteq v（g）$是$（q，k）$ - 如果每个分离$（a，b）$（a，b）$的订单最多$ k $ in $ g $ in $ g $满足$ | a \ cap x | \ leq q $或$ | b \ cap x | \ leq Q $。在本文中，我们证明了以下结果：如果图$ g $不包括固定的完整图$ k_h $作为未成年人并满足某些无法破坏的能力保证，则$ g $在以下意义上几乎是僵化的：$ g $的顶点可以用同态式的方式分配给一个构成界限的一部分，以构成界限的一部分，以构成界限的一部分，并属于一个属于一个属于一个属于一个属于一个属于一个属于的群体，以归为一部分。该结果是图形同构的固定参数算法中的关键成分，该算法由图形的Hadwiger编号参数（伴随论文中呈现）。
A set $X \subseteq V(G)$ in a graph $G$ is $(q,k)$-unbreakable if every separation $(A,B)$ of order at most $k$ in $G$ satisfies $|A \cap X| \leq q$ or $|B \cap X| \leq q$. In this paper, we prove the following result: If a graph $G$ excludes a fixed complete graph $K_h$ as a minor and satisfies certain unbreakability guarantees, then $G$ is almost rigid in the following sense: the vertices of $G$ can be partitioned in an isomorphism-invariant way into a part inducing a graph of bounded treewidth and a part that admits a small isomorphism-invariant family of labelings. This result is the key ingredient in the fixed-parameter algorithm for Graph Isomorphism parameterized by the Hadwiger number of the graph, which is presented in a companion paper.
