论文标题
关于定向和2美元的$ 2 $边缘图的同构的存在和不存在，以反射目标
On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets
论文作者
论文摘要
我们认为非平凡的同态对反射为导向的图形，其中一对相邻的顶点具有相同的图像。使用凸度的概念，用于定向图，我们研究了那些不接受此类同态的定向图。我们将那些不承认这种同质性的宽度$ 2 $的面向宽度的图表完全分类，并表明确定图形是否承认不接受此类同构的方向是NP完整的。我们证明了$ 2 $边缘色的图形的类似结果。我们将结果应用于定向图上，以在研究平面图的色度方向研究中提供新工具，这是一个长期存在的开放问题。
We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. Using a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width $2$ that do not admit such homomorphisms and show that it is NP-complete to decide if a graph admits an orientation that does not admit such homomorphisms. We prove analogous results for $2$-edge-coloured graphs. We apply our results on oriented graphs to provide a new tool in the study of chromatic number of orientations of planar graphs -- a long-standing open problem.
