Duality and $\chi$-Boundedness of Ordered Graphs

Put $\chi(G)=k$. Obviously, by the algorithm, the greedy algorithm finds a $k^{\prime}$-colouring for $k^{\prime}\geq k$.

We prove $k^{\prime}=k$ by an induction on $k$. For $k=1$ the graph is just a single interval.

In the induction step let $\chi(G)=k+1$ and let $I_{1},I_{2},\ldots,I_{k}$ be an optimal colouring. Consider the interval $I^{\prime}_{1}$ given by the greedy algorithm. Clearly $I_{1}\subseteq I^{\prime}_{1}$ and thus $G^{\prime}=G-I^{\prime}_{1}$ (with the vertex set $I^{\prime}_{1}$ deleted) satisfies $\chi(G^{\prime})=k$ and the greedy algorithm produces also a $k$-colouring. Thus also $k+1$ is the result of the greedy algorithm. ∎

As the Greedy algorithm goes over all vertices of $G$ and at each step it checks whether the vertex is not connected to some of the vertices before, the complexity of an algorithm is at most $\mathcal{O}(|G|^{2})$. ∎

By definition, the ordered homomorphism from $G$ to $H$ must preserve an ordering $<_{G}$ as well as edges of $G$, therefore the observation follows. ∎

We will first show that $M_{k}$ and $K_{k}$ are a singleton. From Observation 2.3, we see that $M_{k}\not\to K_{k}$, as $K_{k}$ has at most $k-1$ non-intersecting edges and $M_{k}$ would need at least $k$. Therefore if $M_{k}\to G$ then $G\not\to K_{k}$.

On the other hand, if $M_{k}\not\to G$, then we use the greedy algorithm on $G$ and Proposition 2.1 to get ordered graph $A_{g}$ on minimum number of $g$ vertices. $A_{g}$ will of course contain a directed path $P_{g}$ (as we took all the partition classes maximal). It is clear that $g-1<k$, as otherwise $M_{k}\to A_{g}$, and therefore also to $G$, as $M_{k}\to A_{g}$ maps non-intersecting edges of $M_{k}$ to non-intersecting edges of $A_{g}$, therefore $M_{k}$ could map to these edges in $G$. Hence as $G\to A_{g}\to K_{k}$ (as $A_{g}$ is on $k$ or less vertices), we get $G\to K_{k}$.

Now we shall prove that there does not exist any other duality pair. Let $F$ and $H$ be ordered cores satisfying $F\not\to G$ if and only if $G\to H$ and $F$ and $H$ are not equal to $M_{k}$ and $K_{k}$, resp.

Let $G$ be any ordered matching. We see that if $F\to G$, then $F$ must contain partitions that map to an ordered matching. But then $G$ and $F$ must contain an ordered matching $M_{k}$, for which the ordered homomorphism $F$ to $M_{k}$ is onto. But then $M_{k}$ is the core of $F$.

Now, if there is no homomorphism from $F$ to any ordered matching, then there does not exist any ordered graph $H$, for which there exists ordered homomorphism from ordered matching to $H$, as ordered matchings can require a homomorphic image of any size. E.g. already for $F$ being a $P_{3}$ or $K_{3}$, with $G$ being an ordered matching, we can see that there is no ordered homomorphism from $F$ to $G$, yet we can get $\chi(G)$ of any size by increasing $n$ in $M_{n}$.

We also see that if we forbid an ordered homomorphism from $M_{k}$ to $G$, then $K_{k}$ is the only graph satisfying $M_{k}\not\to G$ if and only if $G\to K_{k}$. ∎

Let us choose a subgraph $M_{k}$ of $G$, where $k$ is maximum, and run the Greedy Algorithm on $G$. As a result of this procedure we will get an ordered graph $A_{g}$, where $|A_{g}|=\chi(G)$ from 2.1. As in 3.1, $A_{g}$ will contain a directed path $P_{g}$. We also see from Observation 2.3 that the $M_{k}$ edges will map to non-intersecting edges in $A_{g}$, as they were non-intersecting in $G$ (where in $G$ they did not share a common vertex).

Now let us assume that $\chi(G)>2k+1$. Then $A_{g}$ will have at least $2k+2$ vertices and it will contain $P_{2k+2}$. But then $P_{2k+2}$ contains an ordered matching of size $k+1$, which should have been chosen in $G$ initially. ∎

Let us first define a size of an edge $\{v_{i},v_{i+j}\}$ as $j$ and a distance in between vertices $v_{i}$ and $v_{i+j}$ as $j$ as well.

We shall start with an easy observation that none of the ordered graphs $K_{m},M^{RL}_{k},M^{+}_{l}$ can be an induced subgraph of $M_{n}$. This is due to the fact that there are always more edges in these graphs than in any induced subgraph of $M_{n}$ that has more than $3$ vertices (as $K_{m},M^{RL}_{k},M^{+}_{l},m\geq 2,m,l\geq 3$ have more than three vertices).

We can also see that none of $M_{n},M^{RL}_{k},M^{+}_{l}$ can be an induced subgraph of $K_{m}$, as $M_{n},M^{RL}_{k},M^{+}_{l}$ are at least on four vertices and their first four vertices do not form a complete graph, which is always the case for any induced subgraph of $K_{m}$.

Let us show that $M^{RL}_{k}$ does not contain $M_{n},K_{m},M^{+}_{l}$ as induced subgraphs.

We notice that $M^{RL}_{k}$ contains $2k$ vertices and directed path $P_{2k}$ on all of these vertices. We will call the set of edges in $P_{2k}$ the path edges and we will call all the other edges (of size longer than one) long edges. We shall notice that all of the path edges are of size one and all the long edges are of odd size of at least three (from definition). Therefore there are no edges of even size.

We will first show that $M^{RL}_{k}$ does not contain a triangle. As there are no edges of even size in $M^{RL}_{k}$, every edge will connect even and odd vertex. As every triangle needs three vertices, it will contain at least two even or two odd vertices. But these vertices would need an even edge to connect them.

Let us now show that $M^{RL}_{k}$ does not contain induced ordered matching of size two. There are three possible cases of such a matching. Having both path edges, both long edges or having one path edge and one long edge of $M^{RL}_{k}$, all pairs of edges of course non-intersecting (without common vertex).

Let us first introduce a notation for a path edge as $e_{i}=\{v_{i},v_{i+1}\}$. In case the induced matching of size two would be containing both path edges, these edges of course could not be consecutive ($e_{i}$ and $e_{i+1}$) and they could not be edges $e_{i}$ and $e_{i+2}$ as they would have another path edge $e_{i+1}$ in between them. Therefore, these edges would need to be $e_{i}$ and $e_{i+j}$ with $j>2$. But all of these path edges are connected by a long edge.

If we consider an induced matching of size two consisting of two long edges, we notice that these will of course need to have each left vertex of each of these edges at different even vertices. But we see that every two non-intersecting edges with different even left vertex will be connected by an edge connecting the first vertex of the first edge and the second vertex of the second edge (as their distance is odd and greater than two).

The last case of induced matching of size two consists of one path edge $r$ and one long edge $s$. We notice that there are two case. One where path edge $r$ is on the left and one where it is on the right side of the long edge $s$.

In case path edge $r$ is on the left, long edges coming from the even vertex of path edge $r$ (whether it is the first or the second vertex of it) will connect $r$ with the second vertex of the long edge $s$, again as long edges in $M^{RL}_{k}$ connect even vertex on the left and odd vertex on the right, if the distance in between them is longer than two.

If path edge $r$ is on the right, we will notice that its odd vertex will connect it with left vertex of every long edge $s$ on the left side of the path edge $r$, as this vertex is even and distance in between them is again longer than two.

Let us show that $M^{RL}_{k}$ does not contain $M^{+}_{l}$ as an induced subgraph. We see that by taking vertices $b_{1},a_{2},b_{2},a_{3}$ in $M^{RL}_{k},k\geq 3$ we get $M^{+}_{2}$. Therefore $M^{+}_{l}$ needs to have $l\geq 3$.

We can also observe that in $M^{RL}_{k},k\geq 2$ every edge (path or long) connects two vertices, out of which one vertex can have long edges connecting this vertex to the vertices on the right and another vertex does not have any long edges connecting it to the vertices on the right (by definition). Another observation is that when choosing an induced subgraph $G$ of $M^{RL}_{k},k\geq 2$, this subgraph will need to contain a directed path $P_{|G|}$, as $M^{+}_{l},l\geq 3$ always contains a directed path $P_{|M^{+}_{l}|}$. We then observe that $M^{+}_{l}$ always contains edges $(a_{1},b_{1}),(a_{1},b_{n}),(a_{n},b_{n}),(b_{1},a_{n})$, where $(a_{1},b_{n}),(b_{1},a_{n})$ are long edges connecting the first vertex with the last one and second vertex with the one vertex before the last one.

But then whichever induced subgraph $G$ we take in $M^{RL}_{k},k\geq 2$, the first two vertices will need to be connected, as there needs to be a path $P_{|G|}$ within $G$. $G$ will also need to contain at least $6$ vertices (because of the minimum order of $M^{+}_{l},l\geq 3$), and therefore first two vertices of $G$ will need to be connected to the last two vertices by long edges of size $|G|-1$ and $|G|-3$. But as we have shown, every edge in $M^{RL}_{k}$ contains a vertex, which is not connected to the vertices on the right by a long edge. Therefore as the first and second vertex in $G$ are connected by a path edge, one of the first two vertices in $G$ is not connected to neither of the last two vertices.

Let us show that $M^{+}_{l},l\geq 3$ does not contain $M_{n},K_{m},M^{RL}_{k},n,k\geq 2,m\geq 3$ as induced subgraphs. The proof of the first two ordered induced subgraphs $M_{n},K_{m}$ goes essentially the same as before.

We notice that $M^{+}_{l}$ contains $2l$ vertices and directed path $P_{2l}$. Again, all of the path edges are of size one and all the long edges are of odd size of at least three (by definition). Therefore, there are no edges of even size also in $M^{+}_{l}$.

We will first show that $M^{+}_{l}$ does not contain a triangle. As observed before, as there are no edges of even size in $M^{+}_{l}$ either, every edge will connect even and odd vertex. As every triangle needs $3$ vertices, it will again contain at least two even or two odd vertices and these vertices would need an even edge to connect them.

Let us now show that $M^{+}_{l}$ does not contain induced matching of size $2$. There are again three possible cases of such an induced matching - having both path edges, both long edges or having one path edge and one long edge in $M^{+}_{l}$, all the three cases again non-intersecting without common vertex in $M^{+}_{l}$.

In case the induced matching of size $2$ would be containing both path edges, we notice that these edges could not be consecutive again ($e_{i}$ and $e_{i+1}$) and they could not be edges $e_{i}$ and $e_{i+2}$ as they would have another path edge $e_{i+1}$ in between them. Therefore, these edges would need to be $e_{i}$ and $e_{i+j}$ with $j>2$. But all of these path edges are connected by a long edge.

If we consider the induced matching of size $2$ consisting of two long edges, then there are 3 cases.

• •

  Left vertex of each of the long edges is at different odd vertices.

• •

  Left vertex of each of the long edges is at different even vertices.

• •

  Left vertex of one of the long edges is at odd vertex and left vertex of another long edge is at even vertex.

For the first case, we see that every two long edges with different odd left vertex will be connected by an edge in between the first vertex of the first edge and second vertex of the second edge (and also by an edge in between second vertex of the first edge and first vertex of the second edge).

For the second case, we see that every two long edges with different even left vertex will be also connected by first vertex of the first edge and second vertex of the second edge (and also by an edge in between second vertex of the first edge and first vertex of the second edge).

In the last case, these edges will be connected by an edge in between the first vertex of the first edge and the first vertex of the second edge (and also by an edge in between the second vertex of the first edge and the second vertex of the second edge).

The last case of induced matching of size $2$ consists of one path edge $r$ and one long edge $s$. We notice that there are two case. One where path edge $r$ is on the left and one where it is on the right side of the long edge $s$.

In case path edge $r$ is on the left, we can see that vertices of $r$ are connecting this edge to all the vertices on the right from $r$ (by definition), therefore $r$ must be connected to $l$ by an edge in $M^{+}_{l}$.

If path edge $r$ is on the right, we will notice that $l$ will have one odd and one even vertex. But then also $l$ is connected to all the vertices on the right from $l$ (again by definition), so $l$ must be connected to $r$ by an edge in $M^{+}_{l}$.

For the proof that $M^{+}_{l},l\geq 3$ does not contain $M^{RL}_{k},k\geq 2$ as induced subgraph, we first notice that first vertex of the $M^{RL}_{k}$ is not connected to other vertices on the right by a long edge. We also notice that $M^{RL}_{k}$ has at least four vertices and that $M^{RL}_{k}$ always contains a directed path $P_{2k}$.

Therefore any induced ordered subgraph $G$ of $M^{+}_{l}$ will also always need to contain a path $P_{4}$ on the first $4$ vertices. We also notice that for every vertex $v_{i}$ in $M^{+}_{l}$, vertex $v_{i}$ is connected to all the vertices, with odd distance that is greater than $2$ (from definition), on the right from $v_{i}$.

This means that as the edges in $M^{+}_{l}$ are all of the odd size, whichever edges we pick in $M^{+}_{l}$ to form the directed path $P_{4}$ on the first four vertices of $M^{RL}_{k}$, the sum of the sizes of these edges in $M^{+}_{l}$ will be odd and greater than two, as the sum of three odd numbers is always odd and greater than two. But then the first four vertices of $G$ must have the first and the fourth vertex connected, and as these can be connected only by long edge in $G$, we observed that this cannot be the case for $M^{RL}_{k}$, as $M^{RL}_{k}$ does not have the first vertex connected to any vertices on the right by long edge.

The last thing to show is the coloring of these ordered graphs.

But this is clear, as for $M_{n},n\geq 2$ we map all the pairs of vertices $b_{i},a_{i+1},1\leq i\leq n-1$ to one interval (this is equivalent to running the greedy algorithm on $M_{n}$) and get a directed path $P_{n+1}$ as a minimum homomorphic image of $M_{n},n\geq 2$.

For $M^{RL}_{k},M^{+}_{l},k\geq 2,l\geq 3$ this is also straightforward, as both of these ordered graphs contain a directed path $P_{2k}$ and $P_{2l}$, respectively, and coloring of $K_{m},m\geq 3$ is $m$.

∎

We see from the Theorem 4.1 that forbidding ordered matchings as subgraphs can bound the coloring of the ordered graphs and from Theorem 4.1 and Theorem 3.1, that as the coloring of our input ordered graph $G$ grows, so must grow our ordered matching subgraph $M_{k}$ of $G$ and there are no other ordered graphs with this property.

Let us now take this ordered matching subgraph $M_{k}$ of $G$ and take ordered matching induced subgraph $\tilde{M}_{k}$ of $G$ on the vertices of $M_{k}$.

We see that there can be four different edges in between two doubles of $\tilde{M}_{k}$ and we denote them as follows:

• •

  $LR$ edge, if it connects left vertex of the first double with the right vertex of the second double.

• •

  $RL$ edge, if it connects right vertex of the first double with the left vertex of the second double.

• •

  $LL$ edge, if it connects left vertex of the first double with the left vertex of the second double.

• •

  $RR$ edge, if it connects right vertex of the first double with the right vertex of the second double.

We therefore have $2^{4}=16$ possible ways how two doubles can be connected (with one option being no edges in between them).

Let us denote a set of edges connecting two doubles as e.g. $\{LR,RL,RR\}$, if these two doubles are connected by edges $LR,RL$ and $RR$, and other sets of edges connecting two doubles analogously.

Let us take an ordered graph where all the doubles are connected by the same set of edges (one of $16$). Then these $16$ different ordered graphs correspond to the following five induced graphs:

• •

  If $n$ doubles are not connected by any edge $\{\}$, this results in an induced ordered matching $M_{n}$.

• •

  If $n$ doubles are all connected to each other by an edge $\{LR\}$, we get an ordered graph $M^{LR}_{n}$.

• •

  If $n$ doubles are all connected to each other by an edge $\{RL\}$, we get an ordered graph $M^{RL}_{n}$.

• •

  If $n$ doubles are all connected to each other by edges $\{LR,RL\}$, we get an ordered graph $M^{+}_{n}$.

• •

  The rest of the cases is if $n$ doubles are all connected to each other by edges $\{LL\}$ or $\{RR\}$ or any other sets of edges containing these edges.

  	$\displaystyle\{LL,RR\},\{LL,RL\},\{LL,LR\},\{RR,RL\},\{RR,LR\},\{LL,RR,LR\},$
  	$\displaystyle\{LL,RR,LR\},\{LL,RL,LR\},\{RR,RL,LR\},\{LL,RR,LR,RL\}$

  Then we get a complete ordered graph $K_{n}$ (or bigger complete ordered graph, e.g. $K_{2n}$ on $\{LL,RR,LR,RL\}$ edge set). We can easily see this, as if all the doubles are connected by the vertex on the same side of the double, these vertices will be connected in all doubles, and therefore form a complete graph.

The Ramsey’s Theorem tells us that for any given finite number of colours, $c$, and any given integers $n_{1},\ldots,n_{c}$, there is a number, $R(n_{1},\ldots,n_{c})$, such that if the edges of a complete graph of order $R(n_{1},\ldots,n_{c})$ are coloured with $c$ different colours, then for some $i$ between $1$ and $c$, it must contain a complete subgraph of order $n_{i}$ whose edges are all of colour $i$.

We notice that the ordered matching induced subgraph $\tilde{M}_{k}$ of $G$ can be thought of as such a complete graph $J$, where each double can be thought of as a vertex of $J$, and $2^{4}=16$ possible edge connections can be though of as $16$ possible edge colors of $J$.

Then using the Ramsey’s Theorem we see that for any $j\in\mathbb{N}$, there exists sufficiently large ordered graph $J$, such that $J$ must contain at least one of $16$ complete graphs of order $j$ with all edges of the same color. This complete graph with all edges of the same color will then correspond to $j$ doubles in $\tilde{M}_{k}$ that are all connected to each other by the same edge set, which will result in one of the five induced ordered subgraphs of $\tilde{M}_{k}$. Therefore with growing coloring of $G$ and consequent growing of $\tilde{M}_{k}$ (as we have shown before), also at least one of the five resulting ordered graphs listed above will grow.

We showed in Proposition 4.3 that all of the ordered graphs $M_{n},K_{m},M^{RL}_{k},M^{+}_{l},n,k\geq 2,m,l\geq 3$ are non-induced. We have also shown that their coloring grows with their size.

The last thing to show is that set of ordered graphs $M_{n},K_{m},M^{RL}_{k},M^{+}_{l}$ together with an ordered graph $M^{LR}_{r}$ is not non-induced. But this can be seen by taking the vertices $b_{1},a_{2},b_{3},a_{4},b_{5},a_{6},\ldots$ of $M^{RL}_{k}$ and seeing that resulting induced ordered subgraph is $M^{LR}_{r}$. Therefore the set of induced ordered graphs $M_{n},K_{n},M^{RL}_{n},M^{+}_{n}$ of $G$ is indeed minimal and sufficient to limit the size of $\chi(G)$.

∎

Let us assume an ordered homomorphism from $G$ to $K_{n}$. We can see, that if we impose left, right or double orientation on edge of $G$, this edge can always map to the same edge in $\overleftrightarrow{K}_{n}$ as it did in $K_{n}$. We can also easily see that if there is an ordered homomorphism $\overleftrightarrow{G}$ to $\overleftrightarrow{K}_{n}$, then we can simply forget the directions and replace them by simple edges and we get the same homomorphism from $G$ to $K_{n}$. ∎

As every directed ordered graph $\overleftrightarrow{M_{k}}$ consists of $M^{R}_{a}$, $M^{L}_{b}$ and $M^{D}_{c}$, where $(a+b+c)=k$, the statement follows from Theorem 4.1 and 5.1. ∎

We shall prove this statement by construction.

Let $\overrightarrow{G}$ be an oriented ordered graph on $2n$ vertices $v_{1},v_{2},\ldots,v_{2n}$ with the following edge set (see Figure 3).

We see that $\overrightarrow{G}$ does not contain neither $\overrightarrow{M}_{2}$ nor $\overrightarrow{P}_{3}$ and that every vertex of $\overrightarrow{G}$ has degree $1$.

We notice that every time we map vertices $v_{i-1}$ and $v_{i},2\leq i\leq n$ in ordered homomorphism to one vertex, we cannot map vertices $v_{n+i-1}$ and $v_{n+i}$ to one vertex in the same ordered homomorphism anymore, and vice versa. Therefore we have maximum $n-1$ options to map two vertices into one in ordered homomorphism (as we cannot map vertices $v_{n}$ and $v_{n+1}$ to one vertex). Therefore the order of minimum homomorphism image of $\overrightarrow{G}$ is $2n-(n-1)=n+1$. ∎