1 Introduction↩︎

An oriented graph \(\overrightarrow{G}\) is a directed graph without loops or parallel arcs in opposite directions. Notice that, the definition allows parallel arcs in the same direction between two vertices, however, for our purpose, the extra parallel arcs in the same direction are redundant. Therefore, we can assume that all oriented graphs mentioned in this article have a simple graph as it’s underlying graph. Moreover, given an oriented graph \(\overrightarrow{G}\), we will denote its set of vertices and arcs by \(V(\overrightarrow{G})\) and \(A(\overrightarrow{G})\), respectively. We denote its underlying graph as \(G\), that is, simply by dropping the overhead arrow.

In 1992, Courcelle [1] introduced the concept of oriented coloring and chromatic number in one of his papers from the series which established the illustrious Courcelle’s theorem [2]. A homomorphism of an oriented graph \(\overrightarrow{G}\) to another oriented graph \(\overrightarrow{H}\) is a vertex mapping \(f: V(\overrightarrow{G}) \to V(\overrightarrow{H})\) such that for any arc \(xy \in A(\overrightarrow{G})\), there is an arc from \(f(x)\) to \(f(y)\) in \(\overrightarrow{H}\). In particular, if \(\overrightarrow{G}\) admits a homomorphism to \(\overrightarrow{H}\) and \(\overrightarrow{H}\) has \(k\) vertices, then we say that \(\overrightarrow{G}\) admits an oriented \(k\)-coloring. The oriented chromatic number of \(\overrightarrow{G}\), denoted by \(\chi_o(\overrightarrow{G})\), is the minimum \(k\) for which \(G\) admits an oriented \(k\)-coloring.

An oriented relative clique \(R \subseteq V(\overrightarrow{G})\) of \(\overrightarrow{G}\) is a vertex subset for which any two vertices \(x,y \in R\) must satisfy \(f(x) \neq f(y)\) under any homomorphism of \(\overrightarrow{G}\) to any \(\overrightarrow{H}\). The oriented relative clique number of \(\overrightarrow{G}\), denoted by \(\omega_{ro}(\overrightarrow{G})\), is the maximum \(k\) such that \(\overrightarrow{G}\) contains an oriented relative clique \(R\) having \(|R|=k\). An oriented absolute clique \(A \subseteq V(\overrightarrow{G})\) of \(\overrightarrow{G}\) is a vertex subset for which any two vertices \(x,y \in A\) must satisfy \(f(x) \neq f(y)\) under any homomorphism of \(\overrightarrow{G}[A]\) to any \(\overrightarrow{H}\), where \(\overrightarrow{G}[A]\) is the subgraph of \(\overrightarrow{G}\) induced by the vertex subset \(A\). The oriented absolute clique number of \(\overrightarrow{G}\), denoted by \(\omega_{ao}(\overrightarrow{G})\), is the maximum \(k\) such that \(\overrightarrow{G}\) contains an oriented absolute clique \(A\) having \(|A|=k\).

As both the notions use the condition of two vertices having distinct images under any homomorphism, the following observation due to Klostermeyer and MacGillivray [4] becomes very useful in their study.

From the definitions of the three parameters, a natural relation between them becomes apparent. This relation makes a study of one of these parameters impact the study of the other two.

The definitions of the three parameters are extended to simple graphs and graph families for the ease of presentation of the research results. Let \(p \in \{\chi_o, \omega_{ro}, \omega_{ao}\}\) denote any of the three parameters. Then, for a simple graph \(G\) we have \[p(G) = \max\{p(\overrightarrow{G}): \overrightarrow{G} \text{ is an orientation of } G\}\] and for a family \(\mathcal{F}\) of graphs we have \[p(\mathcal{F})=\max\{p(G) : G \in \mathcal{F}\}.\] Given a family \(\mathcal{F}\) of oriented graphs (resp., graphs), if \(\forall\overrightarrow{G} \in \mathcal{F}\) (resp., all orientations \(\overrightarrow{G}\) of \(G\) for \(G \in \mathcal{F}\)) admits a homomorphism to \(\overrightarrow{H}\), then \(\overrightarrow{H}\) is a bound of \(\mathcal{F}\). Additionally, if no proper subgraph of \(\overrightarrow{H}\) is a bound of \(\mathcal{F}\), then we say that \(\overrightarrow{H}\) is a minimal bound of \(\mathcal{F}\).

1.1 Context and motivation↩︎

The initial problem considered in Courcelle’s work [1] was to find the oriented chromatic number of the family of planar graphs. Courcelle [1] provided an upper bound for oriented chromatic number as \(64 \cdot 3^{63}\) for oriented planar graphs with in-degree at most \(3\), which was soon improved to \(80\) for general oriented planar graphs by Raspaud and Sopena [7]. To date, according to the best known [7], [8] lower and upper bounds of the oriented chromatic number of planar graphs, its exact value is known to lie somewhere between \(18\) and \(80\). The resolution of the problem, that is, finding the exact value of the oriented chromatic number of planar graphs, will provide us with the analogue of the Four-Color Theorem for oriented graphs, while on the other hand, the problem seems difficult to solve and has remained open since \(1994\).

As related sub-problems, the oriented chromatic number of the family, \(\mathcal{P}_g\), of planar graphs having girth at least \(g\) has been given a particular focus [7]–[16]. Naturally, the oriented relative and absolute clique numbers for the same families are studied as well [5], [17]. To give an overview of the state of the art, let us present the related results in Table 1.

Observe that, the problem of finding the exact values of \(\omega_{ao}(\mathcal{P}_g)\) for all \(g \geq 3\) is completely solved. It is worth mentioning that Klostermeyer and MacGillivray [4] showed \(15 \leq \omega_{ao}(\mathcal{P}_3) \leq 36\) and \(\omega_{ao}(\mathcal{P}_4) \leq 14\) in \(2004\). Furthermore, in the same work [4] the authors conjectured \(\omega_{ao}(\mathcal{P}_3) = 15\) and left the determination of the exact value of \(\omega_{ao}(\mathcal{P}_4)\) as an open problem. Later, in [5], the conjecture was positively settled by proving \(\omega_{ao}(\mathcal{P}_3) = 15\) and the open problem was closed by proving \(\omega_{ao}(\mathcal{P}_4) = 6\).

In [17], the oriented relative clique number for the family, \(\mathcal{P}_g\), of planar graphs having girth at least \(g\) was studied for all \(g \geq 3\). In that paper [17], the exact values of \(\omega_{ro}(\mathcal{P}_g)\) is determined for all \(g \geq 5\), while the main results of the same were given by \(15 \leq \omega_{ro}(\mathcal{P}_3) \leq 32\) and \(10 \leq \omega_{ao}(\mathcal{P}_4) \leq 14\). Thus, finding the exact values of \(\omega_{ro}(\mathcal{P}_3)\) and \(\omega_{ro}(\mathcal{P}_4)\) are natural open problems. In fact, these two were later highlighted in the latest survey on oriented coloring by Sopena [18] as major open problems in the domain (see Problem 3 in Section 10: “Open Problems”).

The significance of oriented cliques: The notions of oriented relative and absolute clique number are together referred to as oriented cliques. Even though there are only a handful of articles dedicated to the structural [4], [5], [17] and algorithmic study [20], [21] of oriented cliques, the notion of oriented cliques is natural and important, and they appear (sometimes implicitly) in several research papers on oriented coloring and related topics, namely, papers related to lower bounds for oriented chromatic number [8], [12], [14], [17], [22]–[24], oriented achromatic number [25], [26], deeply critical oriented graphs [27], [28] and the oriented analogue of the degree diameter problem [29]–[32]. Overall, it will not be unfair to claim that the structural understanding of the oriented cliques is a fundamental problem and is worth studying.

The second column of Table 1 shows that the exact values of \(\chi_{o}(\mathcal{P}_g)\) remains unknown for all \(g \in \{3, 4, \ldots, 11\}\). By Remark 5, finding the exact values of \(\chi_{o}(\mathcal{P}_g)\) boils down to finding (minimal) bounds of \(\mathcal{P}_g\) on \(\chi_o(\mathcal{P}_g)\) vertices. In fact, most of the lower and upper bounds in the second column of Table 1 are obtained theoretically by inspecting (explicitly or implicitly) the properties of the minimal bounds of \(\mathcal{P}_g\). One of the major exceptions is the case of \(\chi_{o}(\mathcal{P}_4)\), where the lower bound of \(11\) is achieved by Ochem [14] through a computer check, and hence the result lacks a theoretical proof, implying a natural open problem.

1.2 Our contributions and organisation↩︎

In this article, we present our section-wise contributions as organized below.

• In Section [sec32prelim], we present the definitions, notation, and terminology specific to oriented graphs.

• In Section 3, we prove that the oriented relative clique number for the family of triangle-free planar graphs is \(10\), and hence solve Problem 7 due to Sopena [18]. The proof is novel and lengthy.

• In Section 4, we use oriented cliques to show that any minimal bound of the family of triangle-free planar graphs have minimum degree at least \(10\). As a consequence of this result, we obtain the first theoretical proof of the lower bound \(\chi_o(\mathcal{P}_4) \geq 11\), and thus solve Problem 8. Moreover, we apply the main result of this section to establish improved lower bounds in the context of three other parameters related to oriented graphs, namely, pushable chromatic number, \(2\)-dipath \(L(p,1)\)-span, and oriented \(L(p,1)\)-span (definitions provided in Section 4).

• In Section 5, we conclude this article and present a few possible future directions of study.

Note: A preliminary version of this article was presented as a paper in CALDAM 2020 [33]. This version contains a significant improvement of the proof of Theorem 9 and its presentation along with newer results in Section 4.

2 Preliminaries↩︎

  We follow West [34] for standard graph theory notation. In general, if some particular notation is meaningful for an undirected graph, but not for an oriented graph, then the same, if applied in the context of an oriented graph \(\overrightarrow{G}\), will be actually meant for its underlying graph \(G\). Further, some useful, but non-standard notations are presented below.

Let \(\overrightarrow{G}\) be an oriented graph, and let \(xy\) be an arc of it. Then we say that \(x\) is an in-neighbor of \(y\) and \(y\) is an out-neighbor of \(x\). The set of all in-neighbors and out-neighbors of \(x\) is denoted by \(N^-(x)\) and \(N^+(x)\), respectively. Moreover, in-degree and out-degree of a vertex \(x\) is given by \(d^-(x) = |N^-(x)|\) and \(d^+(x) = |N^+(x)|\), respectively. Two vertices \(x,y\) agree on a third vertex \(z\) if \(z \in N^{\alpha}(u) \cap N^{\alpha}(v)\) for some \(\alpha \in \{+,-\}\). Also \(x,y\) disagree on \(z\) if \(z \in N^{\alpha}(x) \cap N^{\beta}(y)\) for some \(\{\alpha, \beta\} = \{+,-\}\)¹. We say a vertex \(x\) sees a vertex \(y\) if they are adjacent, or they are connected by a directed \(2\)-path. If \(x,y\) are connected by a directed \(2\)-path with the internal vertex of the directed \(2\)-path being \(z\), we say that \(x\) sees \(y\) via \(z\).

A cycle \(C = x_1x_2 \cdots x_k x_1\) is a separating cycle of a connected graph \(G\) if \(G - C\), that is, the graph obtained by deleting the vertices of the cycle \(C\) from \(G\), is disconnected. Moreover, if two vertices \(y\) and \(z\) belong to different components of \(G - C\), then we say that \(C\) separates \(y\) and \(z\).

3 Oriented relative clique number of \(\mathcal{P}_4\)↩︎

In this section we are going to respond to Problem 7 due to Sopena [18] by giving a conclusive answer via proving the following theorem.

The rest of the section is dedicated to the proof of the main result. As the proof is novel and lengthy, and thus we have separated it into relevant subsections for the convenience of the readers. Moreover, there are several figures to improve the readability of the proof.

3.1 Basic set-up of the proof↩︎

Let \(\overrightarrow{H}\) be a minimal counter-example to Theorem 9 with respect to \(|V(\overrightarrow{H})|+|A(\overrightarrow{H})|\). That means, \(\overrightarrow{H}\) is an oriented triangle-free planar graph and its oriented relative clique number is strictly greater than \(10\). Moreover, any other oriented triangle-free planar graph \(\overrightarrow{H'}\) having oriented relative clique number strictly greater than \(10\) must have \(|V(\overrightarrow{H}')|+|A(\overrightarrow{H}')| \geq |V(\overrightarrow{H})|+|A(\overrightarrow{H})|\).

Let us assume that \(R\) is an oriented relative clique of \(\overrightarrow{H}\) having \(\omega_{ro}(\overrightarrow{H})\) many vertices. In particular, \(|R| \geq 11\). For convenience, we will call the vertices of \(R\) as good vertices. On the other hand, the vertices that are not part of \(R\), that is, the vertices from the set \(S= V(\overrightarrow{H}) \setminus R\) are helper vertices. For the rest of this proof, we are going to assume a particular planar embedding of \(\overrightarrow{H}\) and whenever we speak about a subgraph of \(\overrightarrow{H}\), we will assume it to have the induced embedding. Now, we are going to make two observations about the helper vertices which directly follow from the minimality of \(\overrightarrow{H}\).

This enables us to draw some information about the neighborhood of the helper vertices. Next we will recall a result due to Klostermeyer and MacGillivray [4] which provides us some information about the number of good vertices in the neighborhood of a vertex. Notice that, this result was proved by Klostermeyer and MacGillivray [4] (implicitly proved as a part of the proof of Theorem 11 in [4], for a complete proof see [35]).

Continuing in the spirit of the above lemma, we are going to show that it is not possible for \(\overrightarrow{H}\) to contain certain configurations. These forbidden configurations hold the key for the proof.

3.2 Special terms used in the proof↩︎

Given a planar graph and its embedding, any cycle \(C\) is drawn as a simple close curve. By Jordan Curve Theorem, the curve induced by \(C\) divides the plane into two connected (topologically) regions. Usually, in some of the proofs, we will work with a subgraph of \(\overrightarrow{H}\). Moreover, the embedding of this subgraph will be is unique up to continuous deformation, and all the assumptions related to its orientations are taken without loss of generality. Therefore, it is possible for us to draw a generic picture of this subgraph and name the connected regions induced by it in a figure with references. Moreover, if \(F\) denotes such a region, then by “\(F\) is empty” we mean that it does not contain a good vertex, and \(g \in F\) will mean that \(g\) is a good vertex that belongs to \(F\). Also, \(|F|\) will denote the number of good vertices belonging in it.

3.3 Forbidding four good vertices in a neighborhood↩︎

In this subsection, we are going to show that any vertex \(x\) of \(\overrightarrow{H}\) can have at most three good vertices in its neighborhood. To prove so, we will show that if any vertex \(v\) of \(\overrightarrow{H}\) contains four good vertices in its neighborhood, then we arrive to a contradiction, and thus forbid such a configuration in \(\overrightarrow{H}\). However, based on the embedding and the orientation of the configuration, we have to consider a few different cases in the lemmas listed below.

Proof. Without loss of generality, assume that \(v_1, v_2, v_3, v_4\) are arranged in a clockwise order around \(v\) in the planar embedding of \(\overrightarrow{H}\) and that they are in-neighbors of \(v\). Note that \(v_2\) must see \(v_4\) via some \(h_1\) as \(\overrightarrow{H}\) is triangle-free. Observe that the cycle \(vv_2h_1v_4v\) separates \(v_1\), and \(v_3\). Therefore, \(v_1\) is forced to see \(v_3\) via \(h_1\) as they agree on \(v\), and if either of them are adjacent to \(v_2\) or \(v_4\), then it will result in a triangle. Without loss of generality, we may assume that \(v_1, v_2 \in N^-(h_1)\), and that \(v_3, v_4 \in N^+(h_1)\). Furthermore, \(v_1\) must see \(v_2\) via some \(h_2\), and \(v_3\) must see \(v_4\) via some \(h_3\). As \(h_2\) cannot see \(v_4\), it is a helper. Similarly, as \(h_3\) cannot see \(v_2\), it is a helper. See Fig. 1 for pictorial references, whose naming will be followed during the proof.

First suppose that \(F_{11}\) is non-empty. Then the good vertices of \(F_{11}\) must see \(v_3, v_4\) via \(v\), and thus, they must be out-neighbors of \(v\). Notice that, \(F_{32}\) must be empty as a good vertex from it cannot see the good vertices of \(F_{11}\). On the other hand, any good vertices from \(F_0, F_2\) and \(F_{31}\) must see the good vertices of \(F_{11}\) via \(v\) by being its in-neighbor. Therefore, if any of \(F_0, F_2\) and \(F_{31}\) has a good vertex in it, then \(v\) will have five good neighbors agreeing on it which is forbidden by Lemma 1. Hence the regions \(F_0, F_2\) and \(F_{31}\) are all empty. Also, as the good vertices of \(F_{11}\) must be all out-neighbors of \(v\), by Lemma 1 we have \(|F_{11}| \leq 4\). Moreover, as the vertices of \(F_{11}\) cannot see the vertex \(h_1\) in any way, \(h_1\) functions as a helper. As \(\overrightarrow{H}\) has at least \(11\) good vertices, there must be at least two good vertices inside \(F_{12}\). However, as the good vertices of \(F_{12}\) must see \(v_3,v_4\) via \(h_1\) hence have no way to see \(v\), then vertex \(v\) also must be a helper. This forces \(F_{12}\) to have at least \(3\) good vertices. All these good vertices must see \(v_3, v_4\) via \(h_1\) which will force five vertices to agree on \(h_1\), a contradiction. Therefore, the region \(F_{11}\) must be empty. Similarly, one can show that the region \(F_{31}\) must also be empty.

Next suppose that \(F_{12}\) is non-empty. The good vertices from \(F_{12}\) must see \(v_3, v_4\) via \(h_1\). Also, the good vertices in \(F_0, F_2\), and \(F_{32}\) must see the good vertices of \(F_{12}\) via \(h_1\). This means, except for \(v\) and \(h_1\), every good vertex is adjacent to \(h_1\). This implies that at least \(5\) good vertices agree on \(h_1\), a contradiction to Lemma 1. Therefore, the region \(F_{12}\) must be empty. Similarly, one can show that the region \(F_{32}\) must also be empty.

The good vertices from the regions \(F_0\) (resp., \(F_{2}\)) must see \(v_2\) and \(v_3\) (resp., \(v_1\) and \(v_4\)) via \(h_1\) and \(v\). However, a good vertex from \(F_0\) (resp., \(F_2\)) cannot see both \(v_2\) and \(v_3\) (resp., \(v_1\) and \(v_4\)) via \(h_1\), and hence it must be adjacent to \(v\) as well. This means, except for \(v\) and \(h_1\), every good vertex is adjacent to \(v\). This implies that at least \(5\) good vertices agree on \(v\), a contradiction. ◻

Using the above result, we prove the following.

Now we focus on proving that a vertex \(v\) cannot have two good in-neighbors and two good out-neighbors. The proof is divided into two cases. The first case is as follows.

Proof. Suppose that \(v_1\) sees \(v_3\) via some \(h_1\). Then \(v_2\) is forced to see \(v_4\) via \(h_1\) as well. This, without loss of generality, forces the embedding presented in Fig. 3, whose naming will be followed during the proof.

Any good vertex of \(F_i\) must see \(v_{i+2}\) and \(v_{i+3}\) via either \(v\) or \(h_1\), where \(i \in \{0,1,2,3\}\) and the \(+\) operation is taken modulo \(4\). Note that, there are at least \(5\) more vertices in \(\bigcup F_i\), i.e., \(|F_0|+|F_1|+|F_2|+|F_3| \geq 5\). This will force \(v\) or \(h_1\) to become adjacent to \(7\) good vertices among which three disagree with the fourth one on \(v\) or \(h_1\), respectively. This is a contradiction to Lemma 3. ◻

Now we present the second case.

3.4 Forbidding three good vertices in a neighbourhood↩︎

In this subsection, we want to improve the results of the previous subsection. Indeed, the previous results will be used to prove so.

The final lemma in the similar direction follows.

This implies that the graph \(\overrightarrow{H}\) does not have any vertex \(v\) with at least three good neighbors.

3.5 The final part of the proof↩︎

In particular, for any helper \(h\) we have \(d(h) \leq 2\). Thus, using our earlier observation that the degree of \(h\) is at least \(2\), we can conclude that \(d(h)=2\).

Observe that two helpers \(h_1\) and \(h_2\) cannot have \(N(h_1) = N(h_2) = \{u,v\}\). The reason is, both \(h_1\) and \(h_2\) contribute in \(u\) seeing \(v\). Therefore, even if we delete \(h_2\), the set \(R\) still remains an oriented relative clique contradicting the minimality of \(\overrightarrow{H}\).

Now construct a graph \(\overrightarrow{H}^*\) from \(\overrightarrow{H}\) as follows: delete each helper and add an edge between its neighbors. Observe that \(\overrightarrow{H}^*\) is planar, not necessarily triangle-free, with \(V(H^*)\) being the set of good neighbors of \(\overrightarrow{H}\). Also, the degree of a vertex \(v\) in \(\overrightarrow{H}^*\) is greater than or equal to the degree of \(v\) in \(\overrightarrow{H}\). As \(\overrightarrow{H}^*\) is a planar graph, it must have a vertex \(x\) with degree at most five. Therefore, we can say that there exists a good vertex \(x\) in \(\overrightarrow{H}\) having degree at most five. We fix the name of this vertex \(x\) for the rest of this section.

Proof of Theorem 9. Let \(x\) be a good vertex of \(\overrightarrow{H}\) having degree at most five whose existence follows from the above paragraph. Let \(X = R \setminus (N(x) \cup \{x\})\). We know due to Lemma 9 that \(|R \cap N(x)| \leq 2\).

As \(|R| \geq 11\), we have \(|X| \geq 8\). Note that each vertex of \(X\) must see \(x\) via one of its neighbors. Therefore, by pigeonhole principle at least one of the neighbors \(x_1\) of \(x\) will have two good neighbors from \(X\). Thus \(x_1\) has three good neighbors, contradicting Lemma 9. 0◻

4 Properties of minimal bounds of \(\mathcal{P}_4\)↩︎

To begin this section, we will prove that if \(\overrightarrow{T}\) is a minimal bound of \(\mathcal{P}_4\), that is, the family of triangle-free planar graphs, then it is necessary for every vertex of \(T\) to have degree at least \(10\).

Proof. Let \(\overrightarrow{T}\) be a minimal bound of \(\mathcal{P}_4\), that is, the family of triangle-free planar graphs. Thus, there exists a \(\overrightarrow{H} \in \mathcal{P}_4\) such that for any homomorphism \(f: \overrightarrow{H} \to \overrightarrow{T}\) the following are satisfied:

(a) For any \(v \in V(\overrightarrow{T})\), there exists some \(v' \in V(\overrightarrow{H})\) such that \(f(v') = v\).

(b) For any \(uv \in A(\overrightarrow{T})\), there exists some \(u'v' \in A(\overrightarrow{H})\) such that \(f(u') = u\) and \(f(v') = v\).

Next we are going to build a gadget graph recursively for our proof using the triangle-free planar oriented graph \(\overrightarrow{G}_0\) depicted in Fig. 7 as the base graph. Notice that, in \(\overrightarrow{G}_0\), the vertex subset \(|R|= \{x, y, v_1, v_2, \ldots, v_8\}\) is an oriented relative clique of order \(10\). As \(\overrightarrow{G}_0\) is an oriented triangle-free planar graph, it must admit a homomorphism \(g_0\) (say) to \(\overrightarrow{T}\). An important observation to make here is that the images \(g_0(x), g_0(y)\) of \(x, y\), respectively, will also have at least two vertices (common neighbors) in the set \(N^\alpha(g_0(x)) \cap N^\beta(g_0(y))\), for all \(\alpha, \beta \in \{+,-\}\) inside \(\overrightarrow{T}\). As this property is important for the proof, let us define it formally. Two distinct vertices \(u,v\) of \(\overrightarrow{T}\) are in a \(X_2\)-relation if we have \(|N^\alpha(u) \cap N^\beta(v)| \geq 2\) for all \(\alpha,\beta \in \{+,-\}\).

Let us now continue to build our gadget graph further. Recall that there exists an oriented triangle-free outerplanar graph \(\overrightarrow{M}\) with oriented chromatic number \(6\), constructed by Dolama [36]. We construct a mixed graph by adding a vertex \(z\) to the oriented graph \(\overrightarrow{M}\) which is adjacent to each vertex of \(\overrightarrow{M}\) via a (red) edge (depicted in Fig. 8). Now replace each of the (red) edges \(zw\) with the oriented graph \(\overrightarrow{G}_0\). The precise step-wise process of this replacement is: take a copy of \(\overrightarrow{G}_0\), identify its vertex \(x\) (resp., \(y\)) with the vertex \(z\) (resp., \(w\)) of the mixed graph, delete the (red) edge \(zw\). The so-obtained oriented graph is called \(\overrightarrow{G}_1\). Observe that, \(\overrightarrow{G}_1\) is an oriented triangle-free planar graph, and thus it must admit a homomorphism \(g_1\) (say) to \(\overrightarrow{T}\). As the oriented chromatic number of \(\overrightarrow{M}\) is \(6\), and as due to our construction \(g_1(z)\) must be in \(X_2\)-relation with every vertex of \(\overrightarrow{M}\) (sitting inside \(\overrightarrow{G}_1\) as a subgraph), the image \(g_1(z)\) in \(\overrightarrow{T}\) must be in \(X_2\)-relation with at least \(6\) other vertices of \(\overrightarrow{T}\).

After this, take \(|V(\overrightarrow{H})|\) copies of \(\overrightarrow{G}_1\) and for each vertex \(v\) of \(\overrightarrow{H}\), take one copy of \(\overrightarrow{G}_1\) and identify its vertex \(z\) to the vertex \(v\). This so-obtained oriented graph is called \(\overrightarrow{G}_2\). Observe that, as \(\overrightarrow{G}_2\) is an oriented triangle-free planar graph, it must admit a homomorphism \(g_2\) (say) to \(\overrightarrow{T}\). As each vertex of \(\overrightarrow{H}\) (sitting inside \(\overrightarrow{G}_2\) as a subgraph) plays the role of \(z\) in \(\overrightarrow{G}_1\), and as any homomorphism of \(\overrightarrow{H}\) to \(\overrightarrow{T}\) is onto (on the set of vertices), each vertex of \(\overrightarrow{T}\) must be in \(X_2\)-relation with at least \(6\) other vertices.

We are now ready to conclude the proof in the method of contradiction. Thus, let us assume that \(v\) is a vertex of \(\overrightarrow{T}\) satisfying \(d(v) = d^{+}(v) + d^{-}(v) \leq 9\). First of all note that \(d^+(v), d^-(v) \geq 4\) in order for \(v\) to have \(X_2\)-relation with another vertex. Therefore, for some \(\alpha \in \{+,-\}\) we must have \(d^{\alpha}(v) = 4\). As \(v\) has \(X_2\)-relation with at least \(6\) vertices, by the pigeonhole principle, \(v\) must have \(X_2\)-relation with another vertex, suppose \(u\), from \(N^{\alpha}(v)\). This will imply that we have at least two vertices in the set \(A = N^+(u) \cap N^{\alpha}(v)\) and at least two vertices in the set \(B = N^-(u) \cap N^{\alpha}(v)\). Notice that \(A \cap B = \emptyset\) as \(N^+(u) \cap N^-(u) = \emptyset\).

Thus, notice that, \[4 = d^{\alpha}(v) = |N^{\alpha}(v)| \geq |A| +|B| + |\{u\}| \geq 2 + 2 + 1 = 5,\] a contradiction. Therefore, \(d(v) \geq 10\) for all \(v \in V(\overrightarrow{T})\). ◻

4.1 Application 1: oriented chromatic number↩︎

Recall that the bound \(\chi_o(\mathcal{P}_4) \geq 11\) was achieved by Ochem [14] using a computer check. Here, as a corollary of Theorem 12 we obtain a theoretical proof of the same, and slightly improve the result.

According to Remark 5, we know that there exists a minimal bound of \(\mathcal{P}_4\) on \(\chi_o(\mathcal{P}_4)\) vertices. However, for the sake of completeness, and also to facilitate similar proofs in future, let us prove a lemma in a generalized set-up.

A family \(\mathcal{F}\) of (oriented) graphs is complete if given any two (oriented) graphs belonging to it, say \(G_1, G_2 \in \mathcal{F}\), there exists a \(G \in \mathcal{F}\) such that \(G_1, G_2\) are subgraphs of \(G\).

4.2 Application 2: pushable chromatic number↩︎

The notion of pushable homomorphism and chromatic number was introduced by Klostermeyer and MacGillivray [37], and have been studied since in a number of articles [38]–[41].

Let \(\overrightarrow{G}\) be an oriented graph. To push a vertex \(v\) of \(\overrightarrow{G}\) is to reverse the direction of all the arcs incident to \(v\). Moreover, \(\overrightarrow{G}\) is in a push relation with \(\overrightarrow{G'}\) if \(\overrightarrow{G'}\) can be obtained by pushing a set of vertices of \(\overrightarrow{G}\). The pushable chromatic number of \(\overrightarrow{G}\), denoted by \(\chi_p(\overrightarrow{G})\), is the minimum \(\chi_o(\overrightarrow{G}')\) where \(\overrightarrow{G}'\) varies over all oriented graphs that are in push relation with \(\overrightarrow{G}\).

For a simple graph \(G\) we have \[\chi_p(G) = \max\{\chi_p(\overrightarrow{G}): \overrightarrow{G} \text{ is an orientation of } G\},\] and for a family \(\mathcal{F}\) of graphs we have \[\chi_p(\mathcal{F})=\max\{\chi_p(G) : G \in \mathcal{F}\}.\] Even though the bound \(\chi_p(\mathcal{P}_4) \geq 6\) is not proved explicitly anywhere, it follows directly from \(\chi_o(\mathcal{P}_4) \geq 11\), the result obtained by Ochem [14] via a computer check. As we have reproved the same theoretically, the bound \(\chi_p(\mathcal{P}_4) \geq 6\) also have a theoretical proof now.

4.3 Application 3: \(2\)-dipath and oriented \(L(p,q)\) span↩︎

The Channel Assignment Problem (CAP) in wireless network is an important domain of research. There are several graph models proposed for studying CAP using graph theory. One of the popular such graph model of the problem is given by the \(L(p,q)\)-labeling problem [42]. While the \(L(p,q)\)-labeling problem is defined on simple graphs, as its less popular oriented analogue, two models exist in literature and has been studied. Those two models are called the \(2\)-dipath \(L(p,q)\)-labeling and the oriented \(L(p,q)\)-labeling [43], [44].

A \(2\)-dipath \(k\)-\(L(p,q)\)-labeling [43] of an oriented graph \(\overrightarrow{G}\) is a function \(l : V(\overrightarrow{G}) \rightarrow \{0,1,\ldots,k\}\) satisfying

(i) If \(u,v\) are adjacent, then \(|l(u) - l(v)| \geq p\).

(ii) If \(u,v\) are endpoints of a directed \(2\)-path, then \(|l(u) - l(v)| \geq q\).

The \(2\)-dipath \(L(p,q)\)-labeling span of \(\overrightarrow{G}\), denoted by \(\overrightarrow{\lambda}_{p,q}(\overrightarrow{G})\), is the minimum \(k\) such that \(\overrightarrow{G}\) admits a \(2\)-dipath \(k\)-\(L(p,q)\)-labeling. For the family of oriented triangle-free planar graphs, we can prove an improved lower bound of the \(2\)-dipath \(L(p,1)\)-labeling span.

The notion of oriented \(L(p,q)\)-labeling is a result of combining the concepts of \(2\)-dipath \(L(p,q)\)-labeling and oriented coloring [44]. However, in [45] the definition of oriented \(L(p,1)\)-labeling has an equivalent formulation using graph homomorphisms. As our result only concerns oriented \(L(p,1)\)-labeling and its corresponding span, we are going to provide the homomorphism version of the definition.

The graph \(L_{p,k}\) is a graph on the set of vertices \(\{0, 1, \ldots, k\}\), and its two vertices \(i, j\) are adjacent if \(|i-j| \geq p\). An oriented \(k\)-\(L(p,1)\)-labeling [45] of an oriented graph \(\overrightarrow{G}\) is a homomorphism \(h : \overrightarrow{G} \to \overrightarrow{L}_{p,k}\), where \(\overrightarrow{L}_{p,k}\) is any orientation of \(L_{p,k}\). One can note that, apart from being a homomorphism, \(h\) is also a \(2\)-dipath \(k\)-\(L(p,1)\)-labeling as well.

The oriented \(L(p,1)\)-labeling span of \(\overrightarrow{G}\), denoted by \(\lambda^o_{p,q}(\overrightarrow{G})\), is the minimum \(k\) such that \(\overrightarrow{G}\) admits an oriented \(k\)-\(L(p,1)\)-labeling. For the family of oriented triangle-free planar graphs, we can prove an improved lower bound of the oriented \(L(p,1)\)-labeling span.

5 Concluding remarks↩︎

1. If we look at Table 1, which summarizes the best-known bounds of the oriented relative and absolute clique numbers of planar graphs having girth at least \(g \geq 3\), we observe that except for \(\omega_{ro}(\mathcal{P}_3)\), that is, the oriented relative clique number of the family of planar graphs, exact values are known for all cases. Thus, one natural direction of research is to figure out the exact value of \(\omega_{ro}(\mathcal{P}_3)\). This will also answer Problem 6 due to Sopena [18].

2. One interesting observation is that the three parameters, namely, the oriented chromatic number and the oriented clique numbers take three distinct values for the family of triangle-free planar graphs. To be precise, we know that \(\omega_{ao}(\mathcal{P}_4)=6\) [5], \(\omega_{ro}(\mathcal{P}_4) = 10\), and \(\chi_{o}(\mathcal{P}_4) \geq 11\). Thus, one of the most natural questions to ponder in this direction is to figure out the exact value of \(\chi_{o}(\mathcal{P}_4)\). However, it is known to be a difficult problem. Therefore, as an intermediate step towards its resolution, can we improve its existing lower and upper bounds of \(11\) and \(40\)? In particular, can we extend the ideas exercised in the proof of Theorem 12 to characterize all possible minimal bounds of \(\mathcal{P}_4\) on \(11\) vertices? Or possibly, improve the lower bound to \(12\) by showing that there does not exist any such minimal bond of \(\mathcal{P}_4\) on \(11\) vertices? Furthermore, improving the upper bound of \(40\) is yet another challenging question.

3. Finding the tight upper bound for the pushable chromatic number, \(2\)-dipath \(L(p,1)\)-span, and the oriented \(L(p,1)\)-span of an oriented triangle-free planar graph are natural open questions. In fact, improving the lower and upper bounds are challenging questions as well.

Acknowledgements: This work is partially supported by the IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39), “NBHM/RP-8(2020)/Fresh”, SERB-MATRICS “Oriented chromatic and clique number of planar graphs” (MTR/2021/000858).

References↩︎