We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corresponding computational and parameterized complexities, along with algorithms associated with related problems. These questions are interesting, and we show that numerous problems lead to various complexities. The reduction from homomorphisms of unordered structures to homomorphisms of ordered graphs is proved, achieved with the use of ordered bipartite graphs. We then determine the NP-completeness of the problem of finding ordered homomorphisms of ordered graphs and the XP and W[1]-hard nature of this problem parameterized by the number of vertices of the image ordered graph. Classes of ordered graphs for which this problem can be solved in polynomial time are also presented.

翻译：本文从同态（及着色）及其复杂性的角度，研究了具有线性有序顶点的有序图。我们展示了相应的计算复杂性与参数化复杂性，并提供了相关问题的算法。这些问题具有研究价值，我们证明许多问题会引发不同的复杂性。通过使用有序二分图，我们证明了从无序结构同态到有序图同态的归约。随后，我们确定了寻找有序图有序同态问题的NP完全性，以及该问题在参数化为目标有序图顶点数时的XP与W[1]-困难性质。此外，本文还提出了该问题可在多项式时间内求解的有序图类别。