论文标题
通往路径和周期的全摩形态
Full-homomorphisms to paths and cycles
论文作者
论文摘要
一对图之间的全合法形态是一个顶点映射，可保留邻接和非附属物。对于固定的图$ h $，全$ H $颜色是$ g $至$ h $的全部塑性。最小的$ h $ - obstruction是一张不承认完整$ h $颜色的图表，因此每一个适当的诱导子图$ g $都可以承认完整的$ h $颜色。费德（Feder）和地狱（Hell）证明，对于每张图$ h $，都有有限数量的最小$ h $ obstrountions。我们通过描述所有最小路径的障碍来开始这项工作。然后，我们研究了规则图的最小障碍物，以提出描述最小循环障碍物的描述。由于这些结果，我们观察到，对于每个路径$ p $和每个周期$ c $，最小值$ p $ -Obstructions的数量和$ c $ -Obstructions是$ \ Mathcal {o}（| V（p）|^2）$和$ \ \ \ \ \ \ \ \ \ \ \ \ {o}（o}（o}（c）| v（c）|^2）$。最后，我们提出了一些有关最小$ h $ obstructions和最小$ h $ obstructions的数量的问题。
A full-homomorphism between a pair of graphs is a vertex mapping that preserves adjacencies and non-adjacencies. For a fixed graph $H$, a full $H$-colouring is a full-homomorphism of $G$ to $H$. A minimal $H$-obstruction is a graph that does not admit a full $H$-colouring, such that every proper induced subgraph of $G$ admits a full $H$-colouring. Feder and Hell proved that for every graph $H$ there is a finite number of minimal $H$-obstructions. We begin this work by describing all minimal obstructions of paths. Then, we study minimal obstructions of regular graphs to propose a description of minimal obstructions of cycles. As a consequence of these results, we observe that for each path $P$ and each cycle $C$, the number of minimal $P$-obstructions and $C$-obstructions is $\mathcal{O}(|V(P)|^2)$ and $\mathcal{O}(|V(C)|^2)$, respectively. Finally, we propose some problems regarding the largest minimal $H$-obstructions, and the number of minimal $H$-obstructions.
