The Existence of a Path with Two Blocks in Digraphs

Abstract

We give a new elementary proof of El Sahili conjecture El Sahili (Discrete Math 287:151–153, 2004) stating that any n-chromatic digraph D, with $n\ge 4$, contains a path with two blocks of order n.

1 Introduction and Elementary Definitions

A graph G is a couple $G = (V(G), E(G))$ where V(G) is the set whose elements are the vertices of G, and E(G) is the set whose elements are called the edges of G. The neighborhood of a vertex v in a graph G is denoted by $N_G(v)$ (or simply N(v)), and it is defined by $N(v)= \{u \in V(G); \ uv \in E(G)\}$.

A proper coloring of a graph is an assignment of colors to its vertex set so that no two adjacent vertices have the same color. A ${\varvec{k}}$-coloring of a graph is a proper coloring of the graph using k colors. For any graph G, we denote by $\chi (G)$ the smallest integer k such that G has a proper k-coloring.

A digraph D is a couple $D = (V(D), A(D))$, where V(D) is the set of vertices of D and A(D) is its set of arcs. Consider a digraph D. The out-neighborhood of a vertex v of D is denoted by $N^+_D(v)$ (or simply $N^+(v)$), and it is defined by $N^+(v)= \{u \in V(D); \ (v,u) \in A(D)\}$. Similarly, the in-neighborhood of a vertex v of D is denoted by $N^-_D(v)$ (or simply $N^-(v)$), and it is defined by $N^-(v)= \{u \in V(D); \ (u,v) \in A(D)\}$. The out-degree (resp. in-degree) of v in D is $d^+_D(v) = |N^+_D(v)|$ (resp. $d^-_D(v) = |N^-_D(v)|$), and for simplicity we say $d^+(v)$ (resp. $d^-(v)$). A digraph H is said to be an induced subdigraph of D if $V(H) \subseteq V(D)$ and for all vertices u and v of H, (u, v) is an arc of H if and only if (u, v) is an arc of D. Let $S \subseteq V(D)$. If H is an induced subdigraph of D and $V(H) = S$, then we write $H = D[S]$. Let a be an arc. We define $D+a$ (resp. $D-a$) to be the digraph obtained after adding the arc a to D (resp. removing the arc a from D if $a \in A(D)$).

The underlying graph of a digraph D, denoted by G[D], is obtained upon removing all the orientations of the arcs of D. The chromatic number of a digraph D, denoted by $\chi (D)$, is the chromatic number of its underlying graph G[D]. A digraph D is said to be ${\varvec{n}}$ -chromatic whenever $\chi (G[D]) = n$. An arc a of D is said to be monochromatic if its ends have the same color.

In our work, the digraphs considered are finite having neither loops nor multiple edges.

For a directed path $P=v_1 v_2 \cdots v_n$ (also denoted by a $v_1 v_n$-path) in a digraph, $v_1$ is said to be the origin of P, $v_n$ is its end and $v_{i+1}$ is the successor of $v_i$ on P for all $i \in \{1, \ldots ,n-1\}$. A subpath of P, denoted by $P_{[v_i,v_j]}$ with $1 \le i<j \le n$, is the directed path contained in P of origin $v_i$ and end $v_j$. Similarly, a subpath of P, denoted by $P_{]v_i,v_j]}$ (resp. $P_{[v_i,v_j[}$) with $1 \le i<j \le n$, is the directed path contained in P of origin $v_{i+1}$ (resp. $v_i$) and end $v_j$ (resp. $v_{j-1}$).

A block of an oriented path P in a digraph is a maximal directed subpath of P. A ${\varvec{P(k, l)}}$ is defined to be a path with two blocks, where the first block consists of k forward arcs followed by a second block consisting of l backward arcs.

If D is an n-tournament, Thomason in [8] proves that D contains every oriented path of length $n-1$ if n is large enough. Havet and Thomassé give in [6] a refinement of Thomason’s result, proving that this is valid for every tournament except for three cases: the directed 3-cycle, the regular tournament on 5 vertices and the Paley tournament on 7 vertices; where in these cases D contains no antidirected path of length $n-1$.

An outbranching is a connected digraph containing a vertex of in-degree zero which is called the source, and all other vertices are of in-degree one. An outforest F is a digraph such that each connected component is an outbranching. For every u of V(F), ${\varvec{P_{u}(F)}}$ denotes the unique directed path in F starting from a source and reaching u. The level of u in F, denoted by $\ell _{F}(u)$, is the order of $P_{u}(F).$ Define for each $i \ge 1$, ${\varvec{L_{i}(F)=\{u \in V(F); \ell _{F}(u)=i\}}}$. Let $y\in V(F)$, we denote by ${\varvec{T_F(y)}}$ the sub-outbranching in F of source y. Note that any digraph contains a spanning outforest. Let F be a spanning outforest of a digraph D. An arc $(u,v) \in A(D)$ is said to be a backward arc with respect to F whenever $\ell _{F}(u) \ge \ell _{F}(v)$, else it is called a forward arc.

A spanning outforest of a digraph D is said to be a maximal forest if $\sum \limits _{v \in V(D)}\ell _{F}(v)$ is maximal. El Sahili and Kouider [4], after introducing the concept of a maximal forest, proved that it verifies this crucial property: For any backward arc (u, v) with respect to a maximal forest F of a digraph D, F contains a vu-directed path, and we will denote it by ${\varvec{P_{[v,u]}(F)}}$.

Addario et al. [1] defined a final forest of a digraph D to be each spanning outforest of D verifying the previous property.

For any final forest F of a digraph D, it can be easily proved that $L_i(F)$ is stable in D for every $i \ge 1$, and consequently $\ell (F) \ge \chi (D)$, where $\ell (F)$ is the maximum integer i such that $L_i(F)$ is non empty, and this gives a very simple proof of Gallai-Roy Theorem [5, 7]:

Theorem 1.1

Every n-chromatic digraph contains a directed path of length $n-1$.

Starting from any spanning outforest, an algorithmic way to obtain a final forest is described in [1]. Let F be a spanning outforest of a digraph D. The process is done by defining a sequence of spanning outforests, say $F_{1}, \, F_{2},\, \dots , \, F_{n}$ such that $F_1=F$, $F_n$ is final and $F_{i+1}$ is obtained from $F_{i}$ by adding a backward arc (x, y) (relative to $F_{i}$) such that $F_i$ contains no directed yx-path, and by deleting the arc of $F_i$ with head y (if any). $F_{i+1}$ is said to be a rectification of $F_{i}$, and $F_n$ is said to be a closure of F. Note that due to this algorithm, at least one vertex has a strictly higher level afterwards, and so a final forest is reachable since the process of rectification tends to maximize the levels of the vertices of the finite digraph we are dealing with.

El Sahili in [4] introduced the function f(n) defined to be the smallest integer such that any f(n)-chromatic digraph contains all paths P(k, j) with $k + j = n - 1$, and he conjectured that $f(n) = n$. Using maximal forests, El Sahili and Kouider [4] proved that $f(n) \le n+1$. Then, Addario et al. [1] proved the conjecture using the notion of final forests and a generalization of Bondy’s Theorem [2] about strongly connected digraphs.

In this paper, we give a new elementary proof of El Sahili conjecture without using strongly connected digraphs.

2 The Elementary Proof

Theorem 2.1

Every n-chromatic digraph with $n \ge 4$ contains any P(k, l) such that $k+l=n-1; \ k, \ l \in \mathbb {N^*}.$

Proof

Due to symmetry, we may assume that $k \le l$. Let D be an n-chromatic digraph. Suppose that D contains no P(k, l) for some $k, \ l \in \mathbb {N^*}$. Let F be a final forest of D, set $U_i(F)=L_i(F)$ for all $i \in \{1, \dots , k-1\}$, $U_i (F) =\bigcup \limits _{r \ge 0} L_{i+ r (l+1)}(F)$ and denote by $D_i=D[U_i(F)]$ for all $i \in \{k, \dots , k+l\}$. Color the vertices in $U_i(F)$ by the color i for all $i \in \{1, \dots , n-1\}$. Note that if $(u,v) \in A(D_i)$ for some $i \in \{k, \dots , k+l\}$, then $i=k$ and $v \in L_k(F);$ otherwise $P_u(F) \cup P_v(F) \cup (u,v)$ contains a P(k, l). Thus, $U_i(F)$ is stable for every $i \ne k$ and $U_k(F)$ is not stable since $\chi (D)=n$ and $V(D)=\bigcup \limits _{i=1}^ {n-1}U_i(F).$

From now on, v is said to be a bad vertex for every $(u,v) \in A(D_k)$. Moreover, $l(P_{[v,u]}(F)) \ge l+1$ which implies that every vertex $z \in T_F(v)$ is the end of a directed path of length $l+1$, denoted by $Q_z$, and it is contained in $(u,v) \cup P_{[v,u]}(F) \cup P_{[v,z]}(F)$.

Claim 1. For every arc $(u,v) \in A(D_k)$, $\ zz' \notin E(G[D])$ for every $z \in T_F(v)$ and for every $z' \notin T_F(v)$ with $\ell _{F}(z') \ge k$. $\square$

Proof

If $(z,z') \in A(D)$, then $(z,z')$ is a forward arc as F is a final forest, and so $\ell _{F}(z') > \ell _{F}(z) \ge k$. Knowing that $l(P_{z'}(F)) \ge k$, $P_{z'}(F) \cap T_F(v) = \phi$ and $Q_z \subseteq T_F(v)$, so $Q_z \cup (z,z') \cup P_{z'}(F)$ contains a P(k, l); which gives a contradiction. Similarly, one can observe that a P(k, l) will appear in $Q_z \cup (z',z) \cup P_{z'}(F)$ if $(z',z) \in A(D)$. $\square$

It is now clear that the only monochromatic arcs appear in $D_k$, which implies that a proper coloring may be established if we recolor properly $T_F(v)$ for every bad vertex v.

Let $(u,v) \in A(D_k),$ and set $C_v^{F} = P_{[v,u]}(F) \cup (u,v),$ $P_{[v,u]}(F)=v_k v_{k+1} \cdots v_p$ where $v_k=v, \ v_p=u$ and $p=\ell _{F}(u).$

A vertex x in D is said to be rich in F if $\ell _{F}(x) \ge k$ and $N(x) \cap L_i(F) \ne \phi$ for all $i \in \{1, \dots , k-1\}$.

From now on, we may consider the following recoloring. For every bad vertex v, if v is not rich, then recolor it by some color i whenever $N(v) \cap L_i(F) = \phi$ for some $i \in \{1,\dots ,k-1\}.$ Otherwise, if v is bad rich but has no rich neighbor in $U_j(F)$ for some $j \in \{k, \cdots , k+l\},$ then recolor its neighbors in $U_j(F)$, if any,by the suitable colors from $\{1,\dots ,k-1\},$ and finally color v by j. In both cases, $T_{F}(v)$ is colored properly by the colors $\{1, \dots , n-1\}$.

A direct consequence of the previous paragraph states that there exists a rich bad vertex v such that v has a rich neighbor in $U_i(F)$ for every $i \ge k$, which implies that we are concerned now with recoloring $T_F(v)$ properly in this case.

Claim 2. If u is a rich in-neighbor of v in $U_k(F)$, then u is the unique in-neighbor of v in $U_k(F).$

Proof

Suppose that there exists $u' \in U_k(F)$ such that $u' \ne u$ and $(u',v) \in A(D).$ Let $j = min\{i: \ 1 \le i \le k \ \text {and} \ N^+(u) \cap L_i(F) \ne \phi \}$, $x \in N^+(u) \cap L_j(F)$ and $y \in N^-(u) \cap L_{j-1}(F)$ if $j>1$. Clearly, $x \in P_v(F).$ If $j=1$, then the path $(u,x) \cup P_v(F) \cup P_{]v,u']}(F) \cup (u',v)$ contains a P(k, l),  else the path $P_y(F) \cup (y,u) \cup (u,x) \cup P_{[x,v]}(F) \cup P_{]v,u']}(F) \cup (u',v)$ contains a P(k, l);  which gives a contradiction. $\square$

Taking into consideration the proof of Claim 2, $P'_z$ denotes the path $(z,x) \cup P_v(F)$ if $j=1$ and the path $P_y(F) \cup (y,z) \cup (z,x) \cup P_{[x,v]}(F)$ if $j>1$ whenever z is a rich in-neighbor of a bad vertex v.

Set $B = \{v: v \ \text { is a rich bad vertex and has a rich in-neighbor in} \ U_k(F)\}$. Let $v \in B$ and let u be the rich in-neighbor of v in $U_k(F)$. Recall that $C_v^{F} = v_k v_{k+1} \cdots v_p$ where $v_k=v, \ v_p=u$ and $p=\ell _{F}(u).$

Claim 3. For every vertex $v \in B$, the rich neighbors of v belong to $L_i(F)$ for every $i \in \{k+1, \dots , k+l\}.$

Proof

Suppose that there exists a rich neighbor w of v such that $w \in U_i(F) - L_i(F)$ for some $i \in \{k+1, \dots , k+l\}.$ If $w \notin T_F(u),$ then $P'_u \cup P_{[v,w]} (F) \cup vw$ contains a P(k, l), which gives a contradiction. If $w \in T_F(u),$ then consider the path $P'_w \cup P_{[v,u]} (F) \cup (u,v)$ if $(w,v) \in A(D)$ and the path $P_v(F) \cup (v,w) \cup P_{[v,w]} (F)$ otherwise. Note that both paths contain a P(k, l), which gives a contradiction. Let $r \in \{1, \dots ,l\}$. We will consider a recoloring $T_F(v)$ for every $v \in B$ having a non rich neighbor $v_{k+r}$. If v has a rich neighbor x in $U_{k+r}(F)$, then $\ell _{F}(x)=k+r$ by Claim 3. Since $\ell _{F}(x) = k+r$ and $x \ne v_{k+r}$, then $x \notin C_v^F$, and so $N(x) \cap L_i(F) = N^-(x) \cap L_i(F)$ for every $i \in \{1, \dots , k\}$, since otherwise $P'_x\cup C_v^F$ contains a P(k, l) which gives a contradiction.

Let $wz \in E(G[D])$, where $w \in T_{F}(v)-T_{F}(x)$ and $z \in T_{F}(x),$ then $(w,z) \in A(D)$ such that $z=x$ and $\ell _{F}(w)<\ell _{F}(x).$ Otherwise, since $w \notin T_F(x)$, then $Q_w \cap T_F(x) = \phi$. If $(z,w) \in A(D)$, then a P(k, l) appears in $P_y(F) \cup (y,x) \cup P_{[x,z]}(F) \cup (z,w) \cup Q_w$ where $y \in N^-(x) \cap L_{k-1}(F)$, which gives a contradiction. Hence, $(w,z) \in A(D)$, and so $\ell _{F}(w) < \ell _{F}(z)$ as $w \notin T_F(x)$. If $z \ne x$, a P(k, l) appears in $P_y(F) \cup (y,x) \cup P_{[x,z]}(F)\cup (w,z) \cup Q_w$ where $y \in N^-(x) \cap L_{k-1}(F)$.

So for any rich neighbor x of v in $U_{k+r}(F)$, recolor z by $i+1$ for every $z \in T_{F}(x) \cap U_i(F)$ with $i \in \{k+1, \dots , k+l-1\}$, recolor z by k for every $z \in T_{F}(x) \cap U_{k+l}(F)$ and finally recolor the remaining neighbors of v in $U_{k+r}(F)$ by the suitable color from $\{1, \dots , k-1\}.$ Now, $T_F(v)$ will be colored properly if we give v the color $k+r$.

Claim 4. There exists no vertex $v \in B$ such that $v_{k+r}$ is a rich neighbor of v for every $r \in \{1, \dots , l\}$. $\square$

Proof

Let $F_1 = F + (u,v) - (v,v_{k+1})$ if $k =1$ and $F_1 = F + (y,v_{k+1}) + (u,v) - (v,v_{k+1}) - (x,v)$ if $k \ge 2$ where $x \in N^-(v) \cap L_{k-1}(F)$ and $y \in N^-(v_{k+1}) \cap L_{k-1}(F).$ Let $F_c$ be a closure of $F_1.$ Since u(F) is minimal, then $\ell _{F_c}(z)=\ell _{F}(z)$ for all $z \in L_i(F)$, $i \in \{1, \dots , k-1\}$, if any. Thus, $\ell _{F_c}(v_{k+1})=k$ and v is still rich in $F_c.$ Due to the minimality of |B| and maximality of $\sum \limits _{w \in B} h_{F}(w)$, $v_{k+1}$ is bad in $F_c$ and $h_{F_c}(v_{k+1}) = h_{F}(v)$ and so $\ell _{F_c}(v) = \ell _{F}(u).$ Moreover, it can be easily proved that $\ell _{F_c}(v_i) = \ell _{F}(v_i) - 1$ for every $i \in \{k+1, \dots , p\}$. Therefore, $C_{v_{k+1}} ^{F_c} = C_v^{F}.$

Repeating the same reasoning, we can show that $v_i$ plays the same role, that is the l successive vertices of $v_i$ on $C_v^F$ are rich neighbors of $v_i$ and $N(v_i) \cap L_{k-1}(F) = N^-(v_i) \cap L_{k-1}(F)$ for every $i \in \{k+1, \dots , p\}$. Using the fact that $k \le l$ and $n \ge 4$, we get that $l \ge 2$ and so $l(C_v^F) \ge 4$. Moreover, $(v_{k+2}, v_k) \in A(D)$, otherwise a P(k, l) appears in $P_{[v_{k+3}, v_p]}(F) \cup (v_p,v_k) \cup (v_k, v_{k+2}) \cup P_z(F) \cup (z, v_{k+1}) \cup (v_{k+1},v_{k+2})$, where $z \in N^-(v_{k+1}) \cap L_{k-1}(F)$. By symmetry, $(v_{k+1}, v_p) \in A(D)$. Finally, $(v_k, v_{k+l}) \in A(D)$, otherwise $P_{[v_{k+1}, v_{k+l}]} (F) \cup (v_{k+l},v_k) \cup P'_{v_p}$ contains a P(k, l). Thus, there exists $i \in \{ k+2, \dots , k+l-1\}$ such that $(v_i,v_k) \in A(D)$ and $(v_k, v_{i+1}) \in A(D)$. Hence, $P_{[v_{k+2}, v_i]}(F) \cup (v_i,v_k) \cup (v_k,v_{i+1}) \cup P_{[v_{i+1}, v_p]}(F) \cup P_z(F) \cup (z, v_{k+1}) \cup (v_{k+1},v_p)$, where $z \in N^-(v_{k+1}) \cap L_{k-1}(F)$, contains a P(k, l); which gives a contradiction.

Thus, we can say now that D is colored properly using $(n-1)$-colors due to Claim 1, which gives a contradiction.$\square$