We study homomorphisms between ordered graphs, defined as graphs equipped with a total order on the vertices, and demonstrate that, in contrast to unordered graphs, many of their core structural properties simplify considerably. We prove that ordered graphs admit a unique singleton homomorphism duality and introduce the corresponding notion of <-boundedness based on ordered chromatic number. We show that all ordered graphs are <-bounded and establish and prove an ordered graph analogue of the Gyárfás-Sumner conjecture, determining all the forbidden ordered graph classes. Further, we prove a version of the Sparse Incomparability Lemma for ordered graphs and use it to explore the structure of order density and gaps in the ordered homomorphism order. This work identifies monotone matchings as key elements underlying duality, chi-boundedness, order density, and its gaps in this framework.
retract of and that every ordered graph maps to a unique ordered core (up to isomorphism). The structure of ordered cores will help us streamline reasoning about dualities and order density.
A singleton homomorphism duality is a pair (, ) such that ↛ if and only if → for all ordered graphs . We show that for each ordered graph , there exists only one such pair for ordered graphs.
We then define subgraphs that are unavoidable in large chromatic number ordered graphs (see Figure 2).
• Monotone matching is an ordered graph with 2 vertices , , = 1, . . . , , with ordering 1 < 1 < 2 < 2 < . . . < < and edges {, }, = 1, . . . , . are left vertices, are right vertices. • is together with all edges {, }, < . • is together with all edges {, }, < .
• + is just ∪ .
We show that these serve as canonical obstructions and key elements (in case of monotone matchings) in the <-boundedness and duality results for ordered graphs, respectively.
Lastly, let < if → and ↛ . For ordered graphs 1, 2, we say that (1, 2) is a gap if 1 < 2 and there is no , such that 1 < < 2.
This communication states the results; detailed proofs will appear in a forthcoming full version. The
partial version with proofs of duality and <-boundedness results can be found in [
The study of graph homomorphisms has a long tradition in structural combinatorics and theoretical
computer science, starting from early work on graph colorings and constraint satisfaction problems.
The concept of homomorphism duality was developed as a way to characterize the solvability of such
problems via minimal obstructions (see [
A central motivation for our study of ordered graphs lies in the rich categorical and algorithmic
behavior of ordered homomorphisms. Ordered homomorphisms are naturally related to concepts such
as ordered chromatic number, which in turn naturally relates to extremal results; see, e.g. [
Our results attempt to address foundational questions related to homomorphism dualities, chromatic bounds, and order density in the category of ordered graphs. Leveraging the additional order structure, our results provide cleaner and more straightforward characterizations compared to their unordered counterparts. In particular, the unique singleton duality, explicit greedy algorithms for computing chromatic number, <-boundedness, a solution to the Gyárfás-Sumner conjecture in the ordered graphs setting, and exploring the density and gaps in the homomorphism order show that ordered graphs are a promising domain for both theoretical and computational exploration.
3.1. Duality of Ordered Graphs In this section, we prove that the only singleton duality for ordered graphs is (, ), ∈ N, where is a ordered monotone matching and is the ordered complete graph. That is, Theorem 3.1. and is the only pair of ordered cores satisfying ̸→ if and only if → , for any ordered graph .
This is again in sharp contract with much more intricate dualities for the unordered graph
characterized in [
Theorem 3.2. Let be an ordered graph. Let be the maximum monotone matching subgraph of . Then <() ≤ 2 + 1.
This result shows that the size of the largest monotone matching directly bounds the chromatic number of the ordered graph. It also justifies the use of monotone matchings as a bounding template for the following result.
Then we prove a stronger (induced) version of the statement 3.2, again borrowing an idea from unordered graphs, the famous Gyárfás–Sumner conjecture. The conjecture states that for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number of colors.
We shall replace the tree with previously introduced forbidden structures and prove the following statement.
Theorem 3.3. Let be an ordered graph that does not contain any of the following graphs as induced subgraphs:
, , , +, , ≥ 2, , ≥ 3.
Then there exists (, , , ) : N4 → N such that <() ≤ (, , , ).
This corresponds to the well-known conjecture for unordered graphs and provides a clean
characterization in the ordered setting.
3.3. Sparse Incomparability Lemma for Ordered Homomorphisms
In this section, we examine an analogy of the Sparse Incomparability Lemma for ordered graphs. There
are many applications of the Sparse Incomparability Lemma in areas of unordered graphs (see, e.g.,
[
Theorem 3.4. For any ordered graph and ∈ N, there exists an ordered matching ′, such that there exists an ordered homomorphism : ′ → and that for any ordered graph , || ≤ there is an ordered homomorphism : ′ → if and only if there is an ordered homomorphism ℎ : → . 3.4. Order Density of Ordered homomorphisms We analyze the partial order induced by ordered homomorphisms on the class of ordered cores.
As in [
Theorem 3.5. Let ∈ N, 1 be an ordered graph on at most vertices and 2 be an ordered core, where every component of 2 has more than two vertices, and 1 < 2. Then there exists an ordered graph such that 1 < < 2.
Theorem 3.6. Let 1, 2 ∈, 2 = 1 ∪ , where is an isolated edge, and 1 < 2. Then (1, 2) is a gap in partial order under ≤ .
This investigation reveals that while the ordered homomorphism order is often dense, the presence
of vertices ordering (and corresponding restrictions on ordered homomorphisms) introduces gaps not
seen in unordered graphs (again, see [
• Greedy Algorithm Analysis: Used to compute < and to reason about minimal colorings. Its correctness is proven inductively and the result is used also in the proof of the Singleton Duality Theorem 3.1 and the <-boundedness Theorem 3.2. • Singleton Duality Proof (Theorem 3.1): This result is proved using the monotone invariant (), the number of non-intersecting edges in , which ordered homomorphisms must preserve. • Ramsey-Theoretic Argument: Ramsey’s theorem is a key tool to prove the Gyárfás–Sumner conjecture analogy Theorem 3.3. • Sparse Incomparability Lemma (Theorem 3.4): Analogy of the Sparse Incomparability Lemma for unordered graphs is established and proved for ordered graphs. This is in turn used in the construction showing the dense order in Theorem 3.5. • Singleton Duality Applications: We use this result in proving the <-boundedness Theorem 3.2, proving the analogue of the Gyárfás–Sumner conjecture for ordered graphs in Theorem 3.3, as well as investigating order density and its gaps for ordered homomorphisms.
These techniques and results allow us to build minimal obstructions for coloring, simulate coloring processes, and demonstrate density and gaps in ordered homomorphism order.
This work demonstrates that the ordered structure on graphs simplifies many foundational
homomorphism problems. We show that determining a chromatic number of ordered graphs is feasible using an
easy greedy algorithm, which is in sharp contrast to unordered graphs (see [
We provide complete characterizations of singleton dualities, which is significantly simpler, compared
to the unordered graphs setting (see [
We establish and prove <-boundedness for unordered graphs and extend the incomparability lemma
and order density to this context. Monotone matchings emerge as central obstructions and building
blocks underlying the duality and coloring properties of ordered graphs. In the submitted article [
We also examine duality and <-boundedness of ordered relational systems, and show various
complexities and parameterized complexities associated with problems related to the homomorphisms
of ordered graphs and their cores in prepared articles [
Future directions include, e.g., extending the ordered homomorphisms’ order density and gap analysis and further refine (, , , ) in the ordered Gyárfás-Sumner context.