论文标题
NU图的Brightwell-Winkler型表征
A Brightwell-Winkler type characterisation of NU graphs
论文作者
论文摘要
在2000年，Brightwell和Winkler将可拆卸图的特征性描述为图形$ h $，在该图上定义了从$ g $到$ h $的同构中定义的homgraph $ {\ rm hom}（g，h）$，已连接到所有图$ g $。这表明，重新配置版本$ {\ rm concon_ {hom}}（h）$的$ h $ - 颜色问题，其中必须对给定的$ g $决定，无论是否连接$ {\ rm hom}（g，h）$是否已连接，只有$ h $是微不足道的。 我们证明了$ h $扩展问题的重新配置版本的起点相似。其中$ {\ rm hom}（g，h; p）$是由$ h $ -h $ -olourings诱导的$ h $ -h $ h $ -h $ -precolouring $ p $ $ g $ g $ the Reconfuguration版本$ QUENS $ recons $ conement $ conement $ rmm conement，如果$ {\ rm hom}（g，h; p）$连接给定$ h $ - $ p $ a Graph $ g $的$ p $。我们表明，$ {\ rm hom}（g，h; p）$的图形$ h $是$（g，p）$的每一个选择都与$ {\ rm nu} $ graphs连接的。这给出了$ {\ rm nu} $图形的新特征，这是一类不错的图形，对于$ {\ rm csp} $ - 二分法的代数方法很重要。 我们进一步给出了$ {\ rm hom}（g，h; p）$的直径，对于$ {\ rm nu} $ graphs $ h $，并在两个$ {\ rm hom}（g，h; p）$之间的两个顶点之间的最短路径可以在参数化的多项元素时间中找到。我们将结果应用于最短路径重新配置的问题，并显着扩大了最近的结果。
In 2000, Brightwell and Winkler characterised dismantlable graphs as the graphs $H$ for which the Hom-graph ${\rm Hom}(G,H)$, defined on the set of homomorphisms from $G$ to $H$, is connected for all graphs $G$. This shows that the reconfiguration version ${\rm Recon_{Hom}}(H)$ of the $H$-colouring problem, in which one must decide for a given $G$ whether ${\rm Hom}(G,H)$ is connected, is trivial if and only if $H$ is dismantlable. We prove a similar starting point for the reconfiguration version of the $H$-extension problem. Where ${\rm Hom}(G,H;p)$ is the subgraph of the Hom-graph ${\rm Hom}(G,H)$ induced by the $H$-colourings extending the $H$-precolouring $p$ of $G$, the reconfiguration version ${\rm Recon_{Ext}(H)}$ of the $H$-extension problem asks, for a given $H$-precolouring $p$ of a graph $G$, if ${\rm Hom}(G,H;p)$ is connected. We show that the graphs $H$ for which ${\rm Hom}(G,H;p)$ is connected for every choice of $(G,p)$ are exactly the ${\rm NU}$ graphs. This gives a new characterisation of ${\rm NU}$ graphs, a nice class of graphs that is important in the algebraic approach to the ${\rm CSP}$-dichotomy. We further give bounds on the diameter of ${\rm Hom}(G,H;p)$ for ${\rm NU}$ graphs $H$, and show that shortest path between two vertices of ${\rm Hom}(G,H;p)$ can be found in parameterised polynomial time. We apply our results to the problem of shortest path reconfiguration, significantly extending recent results.
