On realizations of point determining graphs, and obstructions to full homomorphisms
On realizations of point determining graphs, and obstructions to full homomorphisms
复制标题
DOI：
10.1016/j.disc.2006.11.026
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
T. Feder;P. Hell
中科院分区：
文献类型：
--
作者：
T. Feder;P. Hell
图是决定不同顶点是否具有不同邻域的点。点决定图H的一个实现是一个点决定图G，使得每个去顶点的点子图G-x与H同构。我们研究了点决定图的精细结构，并得出每个点决定图至多有两个实现的结论。图G到图H的完全同态是一个顶点映射f，使得对于G的不同的顶点u和v，我们有G的一条边当且仅当f(U)f(V)是H的一条边。对于一个固定图H，G的一个全H-染色是G到H的全同态。极小H-障碍是一个不允许全H-染色的图，使得G的每个真导出子图都有一个全H-染色。我们利用我们在点定图上的结果分析了最小H-障碍。我们证明了如果H有k个顶点，则一个有k+1个顶点的图是极小H-障碍当且仅当它是H的实现。我们得出结论：每个极小H-障碍至多有k+1个顶点，且至多有两个有k+1个顶点的极小H-障碍。我们还考虑了允许环的图H的全同态。如果H有ℓ环，且有k个不含环的顶点，则每个极小H-障碍至多有(k+1)(ℓ+1)个顶点，且当k和ℓ都为正时，至多有一个具有(k+1)(ℓ+1)个顶点的极小H-障碍.特别地，对于任何允许环的图H，这产生了全H-可染性的有限禁止子图刻画。
A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations. A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices. We also consider full homomorphisms to graphs H in which loops are allowed. If H has ℓ loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(ℓ+1) vertices, and, when both k and ℓ are positive, there is at most one minimal H-obstruction with (k+1)(ℓ+1) vertices. In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.