A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs

Abstract

Given a graph G, we study the problem of finding the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets consisting of colors of their incident edges. This minimum number is called the 2-distance vertex-distinguishing index, denoted by $\chi '_{d2}(G)$. Using the breadth first search method, this paper provides a polynomial-time algorithm producing nearly-optimal solution in outerplanar graphs. More precisely, if G is an outerplanar graph with maximum degree $\varDelta$, then the produced solution uses colors at most $\varDelta +8$. Since $\chi '_{d2}(G)\ge \varDelta$ for any graph G, our solution is within eight colors from optimal.

1 Introduction

Only simple and finite graphs are considered in this paper. Let G be a graph with vertex set V(G), edge set E(G), maximum degree $\varDelta (G)$ and minimum degree $\delta (G)$. For a vertex v, we use E(v) to denote the set of edges incident to v. So $d_G(v)=|E(v)|$ denotes the degree of v in G. A k-vertex is a vertex of degree k. A leaf is a vertex of degree 1. The distance between two vertices u and v, denoted by $d_G(u,v)$, is the length of a shortest path connecting them if there is any. Otherwise, $d_G(u,v)= \infty$ by convention. If $d_G(u,v)=r$ for $u,v\in V(G)$, then u is called an r-distance vertex or an r-neighbor of v, and vice versa. Moreover, we use $N^r_G(v)$ to denote the set of r-neighbors of v in the graph G. In particular, we simply call a 1-neighbor of v a neighbor of v and abbreviate $N^1_G(v)$ to $N_G(v)$. If no ambiguity arises, $\varDelta (G), d_G(v), d_G(u,v), N^r_G(v),$ and $N_G(v)$ are written as $\varDelta , d(v),d(u,v), N^r(v),$ and N(v), respectively. Let diam(G) denote the diameter of a connected graph G, i.e., the maximum of distances between any pair of different vertices in G. A graph G is called normal if it contains no isolated edges.

A proper edge k-coloring of a graph G is a mapping $\phi : E(G)\rightarrow C=\{1,2,\ldots ,k\}$ such that $\phi (e)\ne \phi (e')$ for any two adjacent edges e and $e'$. For a vertex $v\in V(G)$, let $C_{\phi }(v)$ denote the set of colors assigned to the edges in E(v), i.e., $C_{\phi }(v)=\{\phi (uv)| uv\in E(G)\}$.

In this paper, we study the problem of finding the minimum number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct color sets. This minimum number is called the 2-distance vertex-distinguishing index, denoted by $\chi '_{d2}(G)$.

1.1 Related works

For an integer $r\ge 1$, the r-strong edge chromatic number $\chi '_{s}(G,r)$ of a graph G is the minimum number of colors required for a proper edge coloring of G such that any two vertices u and v with $d(u,v)\le r$ have $C_{\phi }(u)\ne C_{\phi }(v)$. Note that $\chi '_{s}(G,r)$ is well defined if and only if G is normal. This concept was introduced by Akbari et al. [1], and independently by Zhang et al. [17]. The reader is referred to [11, 12] for latest results for large r. Moreover, when $r\ge \mathrm{diam}(G)$, $\chi '_{s}(G,r)=\chi '_s(G)$, where $\chi '_s(G)$ is called the strong edge chromatic number of G and this parameter has been extensively investigated, see [3–5].

The adjacent vertex distinguishing edge chromatic number $\chi '_a(G)$ is precisely $\chi '_s(G,1)$. Zhang et al. [16] first introduced this notion (adjacent strong edge coloring in their terminology). Among other things, they proposed the following challenging conjecture, in which $C_5$ denotes the cycle on five vertices.

Conjecture 1

If G is a normal graph and $G\ne C_5$, then $\chi '_{a}(G)\le \varDelta +2$.

Conjecture 1 was confirmed for bipartite graphs and subcubic graphs [2]. Using probabilistic analysis, Hatami [9] showed that every graph G with $\varDelta >10^{20}$ has $\chi '_{a}(G)\le \varDelta +300$. Wang et al. [15] showed that every graph G has $\chi '_{a}(G)\le 2.5\varDelta$ and every semi-regular graph G has $\chi '_{a}(G)\le \frac{5}{3} \varDelta +\frac{13}{3}$. A graph G is said to be semi-regular if each edge of G is incident to at least one $\varDelta$-vertex. If G is a planar graph, then it is shown in [10] that $\chi '_{a}(G)\le \varDelta +2$ if $\varDelta \ge 12$.

More recently, the first four authors considered in [13] the 2-distance vertex-distinguishing edge coloring of graphs, which can be regarded as a relaxed form of the 2-strong edge coloring. Thus, $\varDelta \le \chi '(G)\le \chi '_{d2}(G)\le \chi '_s(G,2)$. In [13], the 2-distance vertex-distinguishing indices of cycles, paths, trees, complete bipartite graphs, and unicycle graphs were completely determined. Moreover, a nearly-optimal upper bound on the 2-distance vertex-distinguishing index of Halin graphs was also obtained. Especially, the following conjecture was proposed in [13]:

Conjecture 2

For any graph G, $\chi '_{d2}(G)\le \varDelta +2$.

1.2 Our contribution

In this paper, we establish a nearly-optimal algorithm with running time $O(n^3)$ for the 2-distance vertex-distinguishing edge-coloring problem in outerplanar graphs. A planar graph is called outerplanar if it has an embedding in the Euclidean plane such that all the vertices are located on the boundary of the unbounded face. An outerplane graph is a particular drawing of an outerplanar graph on the Euclidean plane. A cycle C is called separating if both its interior and exterior contain at least one vertex of G.

Suppose that G is an outerplane graph. Then the following properties (P1)–(P3) hold. Note that (P3) follows from (P2) easily, whereas the proof of (P2) appeared in [7].

(P1) :

$\delta (G)\le 2$.

(P2) :

G does not contain a subdivision of $K_4$ or $K_{2,3}$ as a subgraph.

(P3) :

G does not contain a separating cycle.

Our algorithm is built on those properties. It gives an upper bound of $\varDelta +8$ for the 2-distance vertex-distinguishing index of outerplanar graphs. This means that the solution given by our algorithm is within eight colors from optimal.

2 Outerplanar graphs with $\varDelta \ge 5$

In this section, we construct an algorithm of cubic time to legally color the edges of an outerplanar graph G with $\varDelta \ge 5$ using at most $\varDelta +8$ colors.

2.1 Ordered breadth first search

A rooted tree T is a tree with a particular vertex r designated as its root. The vertices of a rooted tree can be arranged in layers, with vertices at distances i to the root r forming layer i. Hence, layer 0 consists of the root only. For a vertex v in layer $i\ge 1$, the neighbor of v in layer $i-1$ is called its father and all the neighbors of v in layer $i+1$ are called its sons. Vertices in layer i are ordered from left to right with labels $v_{1}^{i}, v_{2}^{i},\ldots ,v_{l_{i}}^{i}$ so that, for any j, either $v_{j}^{i}$ and $v_{j+1}^{i}$ have the same father, or the father of $v_{j}^{i}$ is to the left side of the father of $v_{j+1}^{i}$.

Let G be a connected outerplane graph. Beginning with a chosen vertex r, we order all vertices clockwise. Calamoneri and Petreschi [6] constructed an algorithm OBFT for G. It is a breadth first search starting from r in such a way that vertices coming first in the cyclic ordering are visited first. Using OBFT, G can be edge-partitioned into a spanning tree T rooted at r and a subgraph H with $\varDelta (H)\le 4$, i.e., $E(G)=E(T)\cup E(H)$ and $E(T)\cap E(H)=\emptyset$. Edges in E(T) and E(H) are called tree-edges and non-tree-edges of G, respectively. This edge-partition is called an OBFT partition. Calamoneri and Petreschi [6] used OBFT partition to determined the L(h, 1)-labeling number of an outerplanar graph. This edge-partition technique was also successfully employed in [14] to study the surviving rate of outerplanar graphs.

The following key lemma was given in [6]:

Lemma 1

Every OBFT partition $T\cup H$ for a connected outerplane graph G has the following properties:

• (1) If $v^i_j$ is adjacent to $v^i_k$ with $j<k$, then $v_{j}^{i}v_{k}^{i}$ is a non-tree-edge, and $k=j+1$.

• (2) If $v_{j}^{i}v_{k}^{i-1}\in E(H)$ and $v_{j}^{i}$ is a son of $v_{r}^{i-1}$, then $k=r+1$ and $v_{j}^{i}$ is the rightmost son of $v_{r}^{i-1}$.

Lemma 1 indicates that every vertex $v^i_l$ has at most two neighbors in layer $i-1$, at most two neighbors in layer i, and at most $d(v^i_l)-1$ neighbors in layer $i+1$.

To give an example of OBFT partition, we consider the outerplane graph $G^*$ depicted in Fig. 1. In Fig. 2, vertex 1 is the root of the tree T produced by OBFT and solid (broken) lines denote tree-edges (non-tree-edges).

Fig. 1

An outerplane graph $G^*$ on 18 vertices

Fig. 2

An OBFT partition of $G^*$

2.2 A legal $(\varDelta +8)$-coloring algorithm

Given a proper edge coloring $\phi$ of a graph G, we say that two vertices u and v are conflict if $C_{\phi }(u)=C_{\phi }(v)$. Hence $\phi$ is 2-distance vertex-distinguishing if and only if there are no conflict pair of vertices at distance 2. For convenience, a 2-distance vertex-distinguishing edge k-coloring is abbreviated as a 2DVDE k-coloring in the following. We say that an edge $uv\in E(G)$ is legally colored if the color assigned to it is different from those of its adjacent edges and no pair of vertices of distance 2 are conflict. Let H be a subgraph of G. A proper edge coloring $\phi$ of H is called a 2DVDE partial coloring of G on H if $C_{\phi }(u)\ne C_{\phi }(v)$ for each pair of vertices $u, v\in V(H)$ with $d_H(u)=d_G(u)$, $d_H(v)=d_G(v)$, and $d_H(u,v)=2$.

Theorem 1

If G is an outerplane graph with $\varDelta \ge 5$, then $\chi '_{d2}(G)\le \varDelta +8$.

Proof

Let G be an outerplane graph with $\varDelta \ge 5$. Without loss of generality, assume that G is connected. By carrying out OBFT, G is edge-partitioned into a rooted spanning tree T with r as its root and a subgraph H with $\varDelta (H)\le 4$. Then we are going to give an algorithm of finding a 2DVDE $(\varDelta +8)$-coloring of G using the color set $C=\{1,2,\ldots ,\varDelta +8\}$. Note that $|C|\ge 13$. Let $u_j$ ($1\le j\le |V(G)|$) be the j-th vertex visited in this OBFT partition, where $u_1=r$. Recall that $E(u_j)$ is the set of edges incident to the vertex $u_j$. Define $E_{j}=E(u_1)\cup E(u_2)\cup \cdots \cup E(u_{j})$, and $G_{j}=G[E_{j}]$, which is the subgraph of G induced by edges in $E_j$.

At Step 1, we color $E(u_1)$ properly with distinct colors in C. Let $j\ge 2$. Suppose that $E_{j-1}$ has been colored such that a 2DVDE partial coloring of G on $G_{j-1}$ has been established. At Step j, we color $E(u_j)$ to form a 2DVDE partial coloring of G on $G_j$. Then we set $j:=j+1$ and continue our coloring procedure. Once all $E(u_j)$’s, for $1\le j\le |V(G)|$, have been colored, a 2DVDE coloring of G using at most $\varDelta +8$ colors is constructed.

By Lemma 1 and the structural property of outerplane graphs, we obtain the following useful observation:

Observation 1

• (i) Let $v^{i+1}_{p}$ be a son of $v^i_{l}$, and $v^{i+1}_{q}$ be a son of $v^i_{h}$ such that $l\le h$. If $v^{i+1}_{p}v^{i+1}_{q}\in E(H)$, then $q=p+1$, and $h=l$ or $h=l+1$.

• (ii) For $j=1, 2, 3$, let $v^{i+1}_{l_j}$ be the son of $v^i_{k_j}$ with $l_1<l_2<l_3$. If $v^{i+1}_{l_1}v^{i+1}_{l_2}, v^{i+1}_{l_2}v^{i+1}_{l_3}\in E(H)$, then $k_1\le k_2\le k_3$, and exactly one of the following cases holds:

• (1) $k_1=k_2=k_3$;

• (2) $k_2=k_1$ and $k_3=k_2+1$;

• (3) $k_3=k_2$ and $k_2=k_1+1$.

Let $u_j=v_l^i$. Let $v_{k}^{i-1}$ be the father of $v_{l}^{i}$. We say that a vertex $z\in V(G)$ is full if all edges in E(z) have been colored in the foregoing steps.

We now begin with constructing a 2DVDE partial $(\varDelta +8)$-coloring of G on $G_j$ using $C=\{1,2,\ldots ,\varDelta +8\}$. Let $d_{G_j}(v^i_l)=p$, $d_{G_{j-1}}(v^i_l)=q$, and $t=p-q$. Then $q\le 3$. When $t=0$, since all edges in $E(v_l^i)$ have been colored, we are done. Thus, in the following discussion, we may assume that $t\ge 1$. For a vertex $y\in V(G)$, let $\mathcal {F}(y)$ denote the set of fully conflict vertices of y when certain edges in E(y) are considered to be colored. Obviously, $|\mathcal {F}(y)|$ is no more than the number of 2-neighbors of y in $G_j$.

Remark 1

No son z of $v^{i-1}_{k+1}$ is in $\mathcal {F}(v^i_l)$, and no neighbor $z^*$ of $v^i_{l-1}$ in layer $i+1$ is in $\mathcal {F}(v^i_l)$.

Proof

In fact, if z or $z^*\in \mathcal {F}(v^i_l)$, then it is easy to derive that $v^i_lv^{i+1}_{k+1}\in E(H)$ or $v^i_lv^i_{l-1}\in E(H)$ and hence $d_{G_j}(v^i_l)\ge 3$. However, z or $z^*$ is a leaf or a 2-vertex in $G_j$. $\square$

The following Claim 1 deals with the number of fully conflict vertices of $v^i_l$ in the subgraph $G_j$. By Remark 1, we need to consider the number of 2-neighbors of $v^i_l$ in layer $i-2$, $i-1$, and i, respectively.

Claim 1

• (a) If $v_k^{i-1}$ has the unique son $v^i_l$, then $v^i_l$ has at most 5 fully conflict vertices.

• (b) If $v_k^{i-1}$ has at least two sons, and $v^i_l$ is the leftmost son of $v_k^{i-1}$, then $v^i_l$ has at most 5 fully conflict vertices.

• (c) If $v_k^{i-1}$ has at least two sons, and $v^i_l$ is the rightmost son of $v_k^{i-1}$, then $v^i_l$ has at most $\varDelta +1$ fully conflict vertices.

• (d) If $v_k^{i-1}$ has at least three sons, and $v^i_l$ is a middle son of $v_k^{i-1}$, then $v^i_l$ has at most $\varDelta -1$ fully conflict vertices.

Proof

We first prove (a). Note that $v^i_l$ has at most two neighbors in layer i. If $v^i_l$ has exactly two neighbors in layer i, then Lemma 1(1) asserts that these two neighbors are $v^i_{l-1}$ and $v^i_{l+1}$, and $v^i_lv^i_{l-1}$ and $v^i_lv^i_{l+1}$ are non-tree-edges. By Observation 1(ii), $v^i_l$ and $v^i_{l-1}$ have a common father, or $v^i_l$ and $v^i_{l+1}$ have a common father, which contradicts the hypothesis that $v^i_l$ is the unique son of $v^{i-1}_k$.

Now assume that $v^i_l$ has exactly one neighbor in layer i. We need to consider two subcases. If $v^i_lv^i_{l-1}\in E(H)$ and $v^i_lv^i_{l+1}\notin E(H)$, then the father of $v^i_{l-1}$ is $v^{i-1}_{k-1}$ by the outerplanarity of G, and $v^i_lv^{i-1}_{k+1}\notin E(G)$ for otherwise G will contain a separating cycle with $v_k^{i-1}$ as an internal vertex, contradicting (P3). Hence $v^i_l$ has at most 5 fully conflict vertices, as shown in Fig. 3a1. If $v^i_lv^i_{l-1}\notin E(H)$ and $v^i_lv^i_{l+1}\in E(H)$, then the father of $v^i_{l+1}$ is $v^{i-1}_{k+1}$ by Observation 1(i). Furthermore, if the father of $v^{i-1}_k$ is $v^{i-2}_h$, and the father of $v^{i-1}_{k+1}$ is $v^{i-2}_s$, then $s=h$, or $s=h+1$ by the outerplanarity of G. First, we claim that $v^i_l$ has at most two 2-neighbors in layer $i-2$. Actually, by Lemma 1(2), $v^{i-1}_k$ has at most two neighbors $v^{i-2}_h$ and $v^{i-2}_{h+1}$ in layer $i-2$, and $v^{i-1}_{k+1}$ has at most two neighbors $v^{i-2}_s$ and $v^{i-2}_{s+1}$ in layer $i-2$. If $s=h$, then $v^i_l$ has at most two 2-neighbors $v^{i-2}_h$ and $v^{i-2}_{h+1}$ in layer $i-2$. If $s=h+1$, then $v^{i-1}_{k+1}v^{i-2}_{s+1}\notin E(G)$ because otherwise G contains a separating cycle with $v^{i-2}_{h+1}$ as an internal vertex, which contradicts (P3). Then $v^i_l$ also has at most two 2-neighbors $v^{i-2}_h$ and $v^{i-2}_{h+1}$ in layer $i-2$. Hence, as shown in Fig. 3a2, a3, $v^i_l$ has at most 5 fully conflict vertices.

Fig. 3

Configurations a1–a6 in Claim 1(a), where black squares denote possible conflict vertices with $v^i_l$

Finally, assume that $v^i_l$ has no neighbor in layer i, that is, $v^i_lv^i_{l-1},v^i_lv^i_{l+1}\notin E(H)$. It is easy to see that there do not exist a vertex x in layer $i-1$ and a vertex y in layer $i+1$ such that $xv^i_l$ and $yv^i_l$ are non-tree-edges, for otherwise G will contain a separating cycle with $v^{i-1}_k$ as an internal vertex. Then $v^i_l$ has at most 5 fully conflict vertices as shown in Fig. 3a4–a6 by Remark 1.

Next we prove (b) and (d). It is easy to inspect from Lemma 1 that $v^i_l$ has the desired properties whatever $v^i_l$ is adjacent to $v^i_{l+1}$, as shown in Fig. 4b, d1, d2. It is worth noticing that in (b), when $v^i_{l+1}$ has two neighbors in layer $i-1$, then the second neighbor, other than $v^{i-1}_k$, must be $v^{i-1}_{k+1}$ by Lemma 1(2).

Fig. 4

Configurations b, d1 and d2 in Claim 1(b) and (d)

Finally, we prove (c). First assume that $v^i_l$ has exactly one neighbor in layer $i-1$, i.e., $v^{i-1}_k$. Thus, $v^i_lv^{i-1}_{k+1}\notin E(G)$. If $v^i_{l}v^i_{l+1}\notin E(G)$, then $v^i_l$ has obviously at most $\varDelta -1$ fully conflict vertices, since each such vertex must be a neighbor of $v^{i-1}_k$. So assume that $v^i_{l}v^i_{l+1}\in E(G)$. Then $v^i_{l+1}$ also has exactly one neighbor in layer $i-1$, i.e., $v^{i-1}_{k+1}$, by the outerplanarity of G. It turns out that $v^i_l$ has at most $(\varDelta -1)+1=\varDelta$ fully conflict vertices, as shown in Fig. 5c1.

Fig. 5

Configurations c1–c3 in Claim 1(c)

Next assume that $v^i_l$ has two neighbors in layer $i-1$. By Lemma 1, these two neighbors are $v^{i-1}_k$ and $v^{i-1}_{k+1}$. If $v^i_lv^i_{l+1}\in E(G)$, then the father of $v^i_{l+1}$ is $v^{i-1}_{k+1}$ by Observation 1(i). Let $v^{i-2}_h$ and $v^{i-2}_s$ be the father of $v^{i-1}_k$ and $v^{i-1}_{k+1}$, respectively. Then $s=h$ or $s=h+1$ by the outerplanarity of G. If $s=h$, then $v^i_l$ has at most $(\varDelta -1)+2=\varDelta +1$ fully conflict vertices, as shown in Fig. 5c2. If $s=h+1$, then $v^{i-1}_{k+1}$ has exactly one neighbor in layer $i-2$ by the outerplanarity of G. Thus $v^i_l$ has at most $(\varDelta -1)+2=\varDelta +1$ fully conflict vertices, as shown in Fig. 5c3. If $v^i_lv^i_{l+1}\notin E(G)$, with the similar argument, we can show that $v^i_l$ has at most $(\varDelta -1)+2=\varDelta +1$ fully conflict vertices. $\square$

Since $\varDelta \ge 5$, Claim 1 implies that $v^i_l$ has at most $\varDelta +1$ fully conflict vertices in every case.

Our project is to legally color the edges in $E(u_j) \setminus \{zu_j|zu_j\in E_{j-1}\}$ in such an order if they exist: (1) $v^i_lv^i_{l+1}\in E(H)$; (2) $v^i_lv^{i+1}_s\in E(H)$; (3) other uncolored edges.

It should be pointed out that if $d_{G_j}(v^i_{l+1})=d_{G}(v^i_{l+1})$, then to construct a 2DVDE partial coloring of G on $G_j$, we must keep the legality of $v^i_{l+1}$, i.e., the color set of $v^i_{l+1}$ is required to differ from those of its fully conflict vertices. To do this, let us estimate the number of fully conflict vertices of $v^i_{l+1}$ or $v^{i+1}_s$, where $v_l^iv_s^{i+1}$ is a non-tree-edge.

Claim 2

If $v^i_lv^i_{l+1}\in E(H)$ and $d_{G_j}(v^i_{l+1})=d_{G}(v^i_{l+1})$, then $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$.

Proof

If $v^{i-1}_k$ is the root, then $v^{i-1}_kv_{l+1}^i\in E(T)$, and $\mathcal {F}(v^i_{l+1})$ consists of at most one vertex $v^i_{l-1}$. Hence $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+ |\mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+1$. So suppose that $v^{i-1}_k$ is not the root. By Observation 1(i), the father of $v^i_{l+1}$ is $v^{i-1}_k$ or $v^{i-1}_{k+1}$.

• Assume that the father of $v^i_{l+1}$ is $v^{i-1}_k$. If $v^i_{l+1}$ has exactly one neighbor in layer $i-1$, i.e., $v_k^{i-1}$, then it is easy to see that $d_{G_j}(v^i_{l+1})=d_{G}(v^i_{l+1})=2$. Note that every 2-neighbor of $v^{i}_{l+1}$ in $N(v^{i-1}_k)\setminus \{v^i_{l-1},v^i_l,v^i_{l+1}\}$ is also a 2-neighbor of $v^i_l$. This implies that $\mathcal {F}(v^i_{l+1})\subseteq \mathcal {F}(v^i_{l})\cup \{v^i_{l-1}\}$, and hence $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+1$. Now suppose that $v^i_{l+1}$ has exactly two neighbors in layer $i-1$, i.e., $v^{i-1}_k$ and $v^{i-1}_{k+1}$. It follows that $v^i_{l+1}v^{i-1}_{k+1}\in E(H)$ and $d_{G_j}(v^i_{l+1})=d_{G}(v^i_{l+1})=3$. Note that the sons of $v^{i-1}_{k+1}$ are of degree at most 2 in $G_j$. Therefore, if $x\in \mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$, then x is just $v^i_{l-1}$, or is the neighbor of $v^{i-1}_{k+1}$ in layer $i-1$ or $i-2$. By Lemma 1, $v^{i-1}_{k+1}$ has at most two neighbors in layer $i-2$, and at most two neighbors in layer $i-1$, whereas someone of these neighbors is $v^{i-1}_k$. Let $v^{i-2}_t$ be the father of $v^{i-1}_k$, and $v^{i-2}_s$ be the father of $v^{i-1}_{k+1}$. Then $s=t$ or $s=t+1$ by the outerplanarity of G. If $s=t$, then $v^{i-2}_t\in \mathcal {F}(v^i_l)\cap \mathcal {F}(v^i_{l+1})$, and hence $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$. If $s=t+1$, then $v^{i-1}_{k+1}$ has exactly one neighbor in layer $i-2$, for otherwise G contains a separating cycle with $v^{i-2}_s$ as an internal vertex, contradicting (P3). We also get that $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$.

• Assume that the father of $v^i_{l+1}$ is $v^{i-1}_{k+1}$. Then $v^i_{l+1}$ has exactly one neighbor in layer $i-1$, for otherwise G contains a separating cycle with $v^{i-1}_{k+1}$ as an internal vertex. Hence $v^i_{l+1}v^{i-1}_{k+2} \notin E(G)$, and $d_{G_j}(v^i_{l+1})=d_{G}(v^i_{l+1})=2$. Let $v^{i-2}_t$ be the father of $v^{i-1}_k$, and $v^{i-2}_s$ be the father of $v^{i-1}_{k+1}$. Then $s=t$ or $s=t+1$ by the outerplanarity of G. We define

  $$\begin{aligned} A= & {} \left\{ v^i_{l-1},v^{i-1}_k, v^{i-1}_{k+2}, v^{i-2}_s, v^{i-2}_{s+1}\right\} ,\\ B= & {} \left\{ z |z\hbox { is a son of }v^{i-1}_{k+1}\hbox { other than }v^i_{l+1} \hbox { with } d_{G_j}(z)=d_{G}(z)=2 \right\} . \end{aligned}$$

Then it is not difficult to see that $|B|\le 1$ and $\mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)\subseteq A\cup B$. If $|B|=1$, say $B=\{w\}$, then $w v^{i-1}_{k+2}$ is a non-tree-edge by the outerplanarity of G. This implies that $v^{i-1}_{k+2}\notin \mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$, for otherwise $v^{i-1}_{k+1}v^{i-1}_{k+2}\in E(G)$ and $d_G(v^{i-1}_{k+2})\ge 3$. Thus, at most one vertex in $B\cup \{v^{i-1}_{k+2}\}$ belongs to $\mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$. Assume that $d_{G_j}(v^{i-1}_k)\ge 3$. If at most one of $v_s^{i-2}$ and $v_{s+1}^{i-2}$ is in $\mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$, then $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$. Otherwise, $v_s^{i-2}, v_{s+1}^{i-2}\in \mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$. Then $v_{k+1}^{i-1}v_{s+1}^{i-2}$ is a non-tree-edge. By the outerplanarity of G, s must be identical to t. Hence, $v_s^{i-2}=v_t^{i-2}\in \mathcal {F}(v^i_l)$, contradicting the assumption that $v_s^{i-2}\in \mathcal {F}(v^i_{l+1})\setminus \mathcal {F}(v^i_l)$. Now assume that $d_{G_j}(v^{i-1}_k)=2$. Then $v^i_lv^i_{l-1}\notin E(G)$, for otherwise G would contain a separating cycle with $v_k^{i-1}$ as an internal vertex. Thus, $v_{l-1}^i\notin \mathcal {F}(v^i_{l+1})$. If $s=t$, then $v^{i-2}_t\in \mathcal {F}(v^i_l)\cap \mathcal {F}(v^i_{l+1})$, and henceforth $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$. If $s=t+1$, then $v^{i-1}_{k+1}$ has exactly one neighbor in layer $i-2$, for otherwise G will contain a separating cycle with $v^{i-2}_s$ as an internal vertex. Consequently, $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3$. $\square$

Claim 3

If $v^i_lv^{i+1}_s\in E(H)$ and $d_{G_j}(v^{i+1}_s)=d_{G}(v^{i+1}_s)$, then $|\mathcal {F}(v^{i+1}_s)|\le 2$.

Proof

By Lemma 1, $v^i_{l-1}$ is the father of $v^{i+1}_s$. All the sons of $v^i_{l-1}$, other than $v_s^{i+1}$, are leaves in $G_j$, and $d_{G_j}(v^{i+1}_s)=d_G(v^{i+1}_s)=2$. Every vertex in $\mathcal {F}(v^{i+1}_s)$ is either a neighbor of $v^i_l$ or $v^i_{l-1}$ in layer $i-1$ or i, or a vertex $x_0$ in layer $i+1$ with $x_0v^i_{l-1}\in E(H)$. Notice that if $x_0$ exists, then $v^i_{l-2}$ is the father of $x_0$ by Lemma 1. Hence, either $d_{G_j}(v^i_{l-2})\ge 3$, or $d_{G_j}(v^i_{l-2})=2$ and $v^i_{l-2}$ has distance 3 to $v^{i+1}_s$. Therefore, at most one of $x_0$ and $v^i_{l-2}$ belongs to $\mathcal {F}(v^{i+1}_s)$. It is easy to see that $x_0$ is unique if it exists by Lemma 1. We need to consider two situations as follows.

Case 1 $v^{i-1}_k$ is the root.

If $d_{G_j}(v^{i-1}_k)=2$, then $v^{i-1}_k$ has exactly two neighbors $v^i_l$ and $v^i_{l-1}$ in layer 1. Thus, $\mathcal {F}(v^{i+1}_s)$ contains at most one vertex, i.e., $v^{i-1}_k$, hence $|\mathcal {F}(v^{i+1}_s)|\le 1$. If $d_{G_j}(v^{i-1}_k)\ge 3$, then since $v^i_l$ has at most two neighbors in layer 1 (including $v^i_{l-1}$), we have $|\mathcal {F}(v^{i+1}_s)|\le 2$.

Case 2 $v^{i-1}_k$ is not the root.

Case 2.1 $v^{i-1}_{k}$ is not the father of $v^i_{l-1}$.

Then $v^{i-1}_{k-1}$ is the father of $v^i_{l-1}$, and $v^i_lv^{i-1}_{k+1}\notin E(G)$, for otherwise G contains a separating cycle with $v^{i-1}_k$ as an internal vertex.

Case 2.1.1 $v^i_lv^i_{l+1}\in E(H)$.

Then $v_k^{i-1}$ is the father of $v^i_{l+1}$ by the outerplanarity of G. Thus, $d_{G_j}(v_k^{i-1})\ge 3$. If $d_{G_j}(v_{k-1}^{i-1})\ge 3$, then $\mathcal {F}(v^{i+1}_s)\subseteq \{x_0,v^i_{l-2}, v^i_{l+1}\}$ and hence $|\mathcal {F}(v^{i+1}_s)|\le 2$ by the above discussion. So suppose that $d_{G_j}(v_{k-1}^{i-1})=2$. If neither $x_0$ nor $v^i_{l-2}$ is in $\mathcal {F}(v^{i+1}_s)$, then $\mathcal {F}(v^{i+1}_s)\subseteq \{v^{i-1}_{k-1}, v^i_{l+1}\}$ and consequently $|\mathcal {F}(v^{i+1}_s)|\le 2$. Otherwise, at least one of $x_0v^i_{l-1}$ and $v^i_{l-2}v^i_{l-1}$ belongs to E(H). Since $d_{G_j}(v_{k-1}^{i-1})=2$, $v^{i-1}_{k-1}$ is not the father of $v^i_{l-2}$, and hence G contains a separating cycle with $v^{i-1}_{k-1}$ as an internal vertex, contradicting (P3).

Case 2.1.2 $v^i_lv^i_{l+1}\notin E(H)$.

Then $v_{l+1}^i\notin \mathcal {F}(v^{i+1}_s)$. If neither $x_0$ nor $v^i_{l-2}$ is in $\mathcal {F}(v^{i+1}_s)$, then $\mathcal {F}(v^{i+1}_s)\subseteq \{v^{i-1}_{k-1}, v^{i-1}_{k}\}$, and so $|\mathcal {F}(v^{i+1}_s)|\le 2$. Otherwise, at least one of $x_0v^i_{l-1}$ and $v^i_{l-2}v^i_{l-1}$ belongs to E(H). Hence $v^{i-1}_{k-1}$ is the father of $v^i_{l-2}$, for otherwise G contains a separating cycle with $v^{i-1}_{k-1}$ as an internal vertex, contradicting (P3). Therefore, $d_{G_j}(v_{k-1}^{i-1})\ge 3$, and hence $\mathcal {F}(v^{i+1}_s)\subseteq \{x_0,v^i_{l-2}, v^{i-1}_{k}\}$. Thus $|\mathcal {F}(v^{i+1}_s)|\le 2$ by the above discussion.

Case 2.2 $v^{i-1}_k$ is the father of $v^i_{l-1}$.

It suffices to show that at most one of $v^i_{l+1}$ and $v^{i-1}_{k+1}$ is in $\mathcal {F}(v^{i+1}_s)$. Assume the contrary, we have $v^i_lv^i_{l+1},v^i_lv^{i-1}_{k+1}\in E(G)$. By Observation 1(i), $v^i_{l+1}$ is the son of $v^{i-1}_{k+1}$. Hence $d_{G_j}(v^{i-1}_{k+1})\ge 3$, and so $v^{i-1}_{k+1}\notin \mathcal {F}(v^{i+1}_s)$, a contradiction. Consequently, $|\mathcal {F}(v^{i+1}_s)|\le 2$.$\square$

Now we continue to construct a 2DVDE partial ($\varDelta +8$)-coloring of G on $G_j$ when $t\ge 1$. It suffices to discuss the following cases, depending on the size of t.

Case 1 $t=1$.

Let x be the neighbor of $v^i_l$ not in $G_{j-1}$. There are two subcases to be disposed as follows:

Case 1.1 x is in layer i.

By Lemma 1, $x=v^i_{l+1}$. Note that $xv_l^i$ has at most $q+2$ adjacent edges in $G_{j-1}$, which are contained in $\{v_l^i v^i_{l-1}, v_l^i v^{i-1}_{k}, v_l^i v^{i-1}_{k+1},$ $xv^{i-1}_{h}, xv^{i-1}_{h+1}\}$, where $v_k^{i-1}$ is the father of $v_i^l$, $v^{i-1}_h$ is the father of x, and $k\le h$. By Observation 1(i), $h=k$ or $h=k+1$. Thus, $xv^i_l$ has at most $q+2\le 5$ forbidden colors when it is considered for legal coloring at Step j.

If $d_{G}(x)>d_{G_j}(x)$, then we need only to legally color $xv^i_l$ with some color in C to form a 2DVDE partial coloring of G on $G_j$. This can be done since $|C|-(q+2+|\mathcal {F}(v^i_l)|)\ge |C|-(q+2+ (\varDelta +1))=\varDelta +8-(\varDelta +6)=2$ by Claim 1. It is worth mentioning that, in this case, we do not need to consider the legality of the vertex x. Now suppose that $d_G(x)=d_{G_j}(x)$. Let us further handle two possibilities:

• Assume that $h=k$. Then $q\le 2$. If $v^i_l$ is the leftmost son of $v^{i-1}_k$, then $|\mathcal {F}(v^i_l)|\le 5$ by Claim 1(b). Since $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3\le 8$ by Claim 2, and $|C|-(q+2+8)\ge 1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$. Otherwise, $v^i_l$ is a middle son of $v^{i-1}_{k}$, we have $|\mathcal {F}(v^i_l)|\le \varDelta -1$ by Claim 1(d), and $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le (\varDelta -1)+3=\varDelta +2$ by Claim 2. Since $|C|-(q+2+(\varDelta +2))\ge 2$, we can legally color $xv^i_l$ with some color in C to form a 2DVDE partial coloring of G on $G_j$.

• Assume that $h=k+1$. Then $v^i_l$ is the rightmost son of $v^{i-1}_k$, and x is the leftmost son of $v^{i-1}_{k+1}$. Then $v^i_{l+1}v^{i-1}_{k+2}\notin E(G)$, for otherwise G has a separating cycle with $v^{i-1}_{k+1}$ as an internal vertex. Hence, $xv_l^i$ has at most $q+1$ adjacent edges in $G_{j-1}$ and $d_G(x)=d_{G_j}(x)=2$. If $v^i_l$ is the unique son of $v^{i-1}_k$, then $|\mathcal {F}(v^i_l)|\le 5$ by Claim 1(a), $|\mathcal {F}(v^i_l)\cup \mathcal {F}(v^i_{l+1})|\le |\mathcal {F}(v^i_l)|+3\le 8$ by Claim 2, and $|C|-(q+1+8)\ge 1$. We can legally color $xv^i_l$ with some color in C. Otherwise, $v^{i-1}_k$ has at least two sons, and $v^i_l$ is the rightmost son of $v^{i-1}_k$. By Claim 1(c), $|\mathcal {F}(v^i_l)|\le \varDelta +1$. We note that if $q=3$, then $v^i_lv^i_{l-1}$ is a non-tree-edge, which implies that $|\mathcal {F}(v^i_l)|\le \varDelta$ by the proof of Claim 1(c). Thus, we always have that $|\mathcal {F}(v^i_l)|+q\le \varDelta +3$. Since $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|+q\le |\mathcal {F}(v^i_l)|+3+q\le \varDelta +3+3=\varDelta +6$ by Claim 2, and $|C|-((\varDelta +6)+1)\ge 1$, we can legally color $xv^i_l$ with some color in C to set up a 2DVDE partial coloring of G on $G_j$.

Case 1.2 x is in layer $i+1$.

Then $xv^i_l$ has at most $q+1\le 4$ forbidden colors. If $d_G(x)>d_{G_j}(x)$, then we can legally color $xv^i_l$ with some color in C, because $|C|-(q+1+|\mathcal {F}(v^i_l)|)\ge |C|-(q+1+ (\varDelta +1))\ge 3$ by Claim 1. Now assume that $d_G(x)=d_{G_j}(x)$. If $d_G(x)=d_{G_j}(x)=1$, then we can give $xv^i_l$ a legal coloring as in the previous case. Otherwise, $d_G(x)=d_{G_j}(x)=2$. By Claim 1, $|\mathcal {F}(v^i_l)|\le \varDelta +1$. By Claim 3, $|\mathcal {F}(x)|\le 2$. Thus, $|C|-(|\mathcal {F}(v^i_l)|+|\mathcal {F}(x)| +q+1) \ge |C|-((\varDelta +1)+2+4)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2 $t=2$.

Let x and y be the neighbors of $v^i_l$ not in $G_{j-1}$. Note that at least one of x and y differs from $v^i_{l+1}$, say $y\ne v^i_{l+1}$. Our proof splits into the following two subcases.

Case 2.1 $x=v^{i}_{l+1}$.

Since $xv^i_l$ has at most $q+2\le 5$ forbidden colors, and $|\mathcal {F}(x)|\le \varDelta +1$ by Claim 1, we can legally color $xv^i_l$ with a color a in C (at the moment, we do not consider whether or not $v^i_l$ has fully conflict vertices because $yv^i_l$ has not been colored). Now $yv^i_l$ still has at most $q+1+1\le 5$ forbidden colors. We assert that $|C|-(|\mathcal {F}(v^i_l)|+|\mathcal {F}(y)|+q+2)>0$, so that $yv^i_l$ can be legally colored with some color in C. Otherwise, by Claims 2-3, we derive that $|\mathcal {F}(v^i_l)|=\varDelta +1$, $|\mathcal {F}(y)|=2$, and $q=3$. Since $q=3$, we see that $v^i_lv^i_{l-1}\in E(H)$, hence $v^i_{l-1}\notin \mathcal {F}(v^i_l)$. Recalling the proof of Claim 1(c), we have $|\mathcal {F}(v^i_l)|\le \varDelta$, a contradiction.

Case 2.2 $x\ne v^{i}_{l+1}$.

Both x and y are in layer $i+1$, say $x=v^{i+1}_{h}$, $y=v^{i+1}_{s}$ with $h>s$. Indeed, $h=s+1$ by Lemma 1. We first legally color $yv^i_l$ with some color $a\in C$, since $yv^i_l$ has at most $q+1\le 4$ forbidden colors, and $|\mathcal {F}(y)|\le 2$ by Claim 3. Then we color legally $xv^i_l$ with some color in $C\setminus \{a\}$, since $xv^i_l$ has at most $q+1\le 4$ forbidden colors, and $|\mathcal {F}(v^i_l)|\le \varDelta +1$ by Claim 1.

Case 3 $t\ge 3$.

Let $x_{1}, x_{2},\ldots ,x_{t}$ be the neighbors of $v^i_l$ not in $G_{j-1}$. Without loss of generality, we may assume that $x_{1}=v^{i}_{l+1}$, $x_{2}=v^{i+1}_s$, $\ldots$, $x_t=v^{i+1}_{s+t-2}$ by Lemma 1. (If $x_1=v^{i+1}_{s-1}$, we have a similar discussion). First, since $x_{1}v^i_l$ has at most $q+2\le 5$ forbidden colors, and $|\mathcal {F}(x_1)|\le \varDelta +1$ by Claim 1, we may legally color $x_{1}v^i_l$. Second, since $x_2v^i_l$ has at most $q+2\le 5$ forbidden colors and $|\mathcal {F}(x_2)|\le 2$ by Claim 3, we may legally color $x_2v^i_l$. Finally, since ${\varDelta +8-q-2 \atopwithdelims ()t-2}\ge {\varDelta +3 \atopwithdelims ()t-2}\ge \varDelta +3$, there exists a subset $C'$ of available colors in C with $|C'|=t-2$, such that $v^i_lv_{s+1}^{i+1},\ldots ,v^i_lv_{s+t-2}^{i+1}$ can be legally colored with $C'$. $\square$

Using the result of Theorem 1, we can describe the following algorithm of finding a 2DVDE $(\varDelta +8)$-coloring of an outerplanar graph G with $\varDelta \ge 5$:

Algorithm: 2DVDE-Color Outerplanar Graphs (I).

Input: A connected outerplanar graph G with maximum degree $\varDelta \ge 5$;

Output: A 2DVDE $(\varDelta +8)$-coloring of G;

• 1. Choose a $\varDelta$-vertex $u_1$ and run an OBFT partition starting from $u_1$.

• 2. Color properly $E(u_1)$ with colors $1, 2, \ldots , \varDelta$.

• 3. Repeat for each vertex $u_j$, from left to right, from top to down: Coloring the edges in $E(u_j)\setminus (E(u_1)\cup E(u_2)\cup \cdots \cup E(u_{j-1}))$ according to Theorem 1.

Theorem 2

Let G be a connected outerplanar graph with $n\ge 2$ vertices and $\varDelta \ge 5$. The algorithm 2DVDE-Color Outerplanar Graphs (I) runs in $O(n^3)$ time.

Proof

First, according to a result of [8], the algorithm of searching a spanning tree T in a graph G by using an OBFT partiton needs O(n) time. Next, the algorithm performed in Theorem 1 is iterated n times. At each iteration, we legally color the edge subset $E^*_j:=E(u_j)\setminus E_{j-1}$. The time complexity to consider in this part includes performing the following four tasks.

• (a) Computing the total number $\tau _1$ of forbidden colors for the edges in $E^*_j$;

• (b) Computing the total number $\tau _2$ of fully conflict vertices for at most three fixed vertices;

• (c) Selecting a subset $C'$ of available colors from $C=\{1,2,\ldots ,\varDelta +8\}$;

• (d) Coloring properly $E^*_j$ with $C'$.

For (a), it follows from the proof of Theorem 1 that $\tau _1\le 5 |E^*_j|\le 5d_G(u_j)\le 5\varDelta$. For (b), Claims 1–3 showed that each vertex x has at most $\varDelta +1$ fully conflict vertices in $G_{j-1}$. Thus, $\tau _2\le 3(\varDelta +1)$. For (c), we need to eliminate at most $\varDelta +7$ color subsets from C, whereas every color subset has at most $\varDelta$ elements. For (d), at most $\varDelta$ edges are required for a legal coloring. The above analysis shows that the total running time of our algorithm is at most $n(5\varDelta +3(\varDelta +1)+\varDelta (\varDelta +7)+\varDelta )=n(\varDelta ^2+16\varDelta +3)= O(n\varDelta ^2)$. Since $\varDelta \le n-1$, our algorithm runs in $O(n^3)$ time. $\square$

3 Outerplanar graphs with $\varDelta \le 4$

In this section, we will present a 2DVDE 10-coloring for an outerplanar graph with maximum degree at most 4 using the color set $C=\{1,2,\ldots ,10\}$. The discussion is similar to the proof of Theorem 1.

Theorem 3

If G is an outerplane graph with $\varDelta \le 4$, then $\chi '_{d2}(G)\le 10$.

Proof

Let G be a connected outerplane graph with $\varDelta \le 4$. Carrying out an OBFT partiton, we edge-partition G into a rooted spanning tree T with r as its root and a subgraph H with $\varDelta (H)\le 4$, where $d_G(r)=\varDelta$. Let $u_j$ ($1\le j\le |V(G)|$) be the j-th vertex visited in OBFT, where $u_1=r$. Define $E_{j}=E(u_1)\cup E(u_2)\cup \cdots \cup E(u_{j})$, and $G_{j}=G[E_{j}]$, which is the subgraph of G induced by the edges in $E_j$.

At Step 1, we color $u_1u_2,u_1u_3,\ldots ,u_1u_{\varDelta +1}$ with colors $1,2,\ldots ,\varDelta$, respectively. Then we color successively $u_2u_3,u_3u_4,\ldots ,u_{\varDelta }u_{{\varDelta +1}}$ with 5, 6, 7 if existed. This is available since $G[\{u_2,u_3,\ldots ,u_{\varDelta +1}\}]$ contains at most three edges by Lemma 1.

At Step j, for $j=2,3,\ldots ,\varDelta +1$, we properly color the uncolored edges in $E(u_j)$ from left to right such that the used colors are selected as follows:

• If j is even, the foregoing colors in the set $\{8, j, j+1, \ldots ,\varDelta , 1, 2, \ldots , j-2\}$ are used;

• If j is odd, the foregoing colors in the set $\{9, j, j+1, \ldots ,\varDelta , 1, 2, \ldots , j-2\}$ are used.

Let $j\ge \varDelta +2$. Assume that $E_{j-1}$ has been colored such that a 2DVDE partial coloring $\phi _{j-1}$ of G on $G_{j-1}$ has been established. At Step j, we will color $E(u_j)$ to find a 2DVDE partial coloring of G on $G_j$. As soon as all $E(u_j)$’s, for $1\le j\le |V(G)|$, have been colored, a 2DVDE coloring of G using at most 10 colors is constructed.

Let $u_j=v_l^i$. Then $i\ge 2$. Let $v_{k}^{i-1}$ be the father of $v_{l}^{i}$, and $v^{i-2}_h$ be the father of $v^{i-1}_k$. Set $d_{G_j}(v^i_l)=d_G(v^i_l)=p$, $d_{G_{j-1}}(v^i_l)=q$, and $t=p-q$. Then $q\le 3$ and $p=t+q\le \varDelta \le 4$. Let us consider the following cases, depending on the size of t.

Case 1 $t=0$.

Since all edges in $E(v_l^i)$ have been colored, we are done.

Case 2 $t=1$.

Let x be the neighbor of $v^i_l$ not in $G_{j-1}$. Without loss of generality, assume that $d_{G_j}(x)=d_G(x)$. In fact, if $d_{G_j}(x)< d_G(x)$, the proof is easier since we do not need to consider whether or not x has fully conflict vertices. There are two subcases as follows:

Case 2.1 x is in layer i.

By Lemma 1, $x=v^i_{l+1}$. Note that $xv_l^i$ has at most $q+2$ adjacent edges in $G_{j-1}$.

Case 2.1.1 $q=3$, i.e., $v^i_lv^i_{l-1}, v^i_lv^{i-1}_{k+1}\in E(H)$.

Then $v^{i-1}_{k+1}$ is the father of x, and $v^i_{l-1}v^{i-1}_k\in E(T)$ by Observation 1. So $d_{G_j}(v^{i-1}_k)\ge 3$. Note that $xv^{i-1}_{k+2}\notin E(G)$ for else G contains a separating cycle with $v^{i-1}_{k+1}$ as internal vertex, contradicting (P3). Let $z^*$ be the forth neighbor of $v^{i-1}_k$ if $d_{G_j}(v^{i-1}_k)=4$. If $v^i_{l-1}v^i_{l-2}\in E(G)$, then $z^*=v^i_{l-2}$ for otherwise G will contain a separating cycle with $v^{i-1}_k$ as internal vertex. Since $v^{i-1}_{k+1}$ has at most two other neighbors except $v_l^i$ and x, say $y_1$ and $y_2$, by the fact that $\varDelta \le 4$, we know that $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,y_1,y_2\}$ and $\mathcal {F}(x)\subseteq \{v^{i}_{l-1},y_1,y_2\}$ by Remark 1. Since $|C|-(q+1+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(3+1+5)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2.1.2 $q=2$ with $v^i_lv^{i-1}_{k+1}\in E(H)$.

Then $v^i_lv^i_{l-1}\notin E(G)$, and $v^{i-1}_{k+1}$ is the father of x by Observation 1. Again, $xv^{i-1}_{k+2}\notin E(G)$ by (P3). Similarly to the previous discussion, $v^{i-1}_{k+1}$ has at most two other neighbors $y_1$ and $y_2$, and $v^{i-1}_{k}$ has at most two other neighbors $z_1$ and $z_2$. This implies that $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,y_1,y_2,z_1,z_2\}$ and $\mathcal {F}(x)\subseteq \{v^{i-1}_{k},y_1,y_2\}$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(2+1+6)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2.1.3 $q=2$ with $v^i_lv^{i}_{l-1}\in E(H)$.

Then $v^i_lv^{i-1}_{k+1}\notin E(G)$. Now the proof splits into the following two cases.

Case 2.1.3.1 $v^{i-1}_k$ is the father of x.

Suppose that $xv^{i-1}_{k+1}\notin E(G)$. Then every 2-neighbor of $v^{i}_{l+1}$ in $N(v^{i-1}_k)\setminus \{v^i_{l-1},v^i_l,v^i_{l+1}\}$ is also a 2-neighbor of $v^i_l$. This implies that $\mathcal {F}(x)\subseteq \mathcal {F}(v^i_{l})\cup \{v^i_{l-1}\}$, and hence $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le |\mathcal {F}(v^i_l)|+1$. Since $|\mathcal {F}(v^i_l)|\le 5$ by Claim 1, and $|C|-(q+1+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(2+1+5+1)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Suppose that $xv^{i-1}_{k+1}\in E(G)$. Then $d_{G_j}(x)=3$, and $v^{i-1}_k$ is the father of $v^i_{l-1}$ by (P3). Moreover, $v^i_{l-1}v^i_{l-2}\notin E(G)$ by (P3) and the assumption that $\varDelta \le 4$, which implies that $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,v^{i-1}_{k+1}\}$ by Remark 1. By Claim 2, $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le |\mathcal {F}(v^i_l)|+3\le 5$. Since $|C|-(q+2+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(2+2+5)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2.1.3.2 $v^{i-1}_{k+1}$ is the father of x.

Then $v^{i-1}_k$ is the father of $v^i_{l-1}$ by Observation 1(ii), so $d_{G_j}(v^{i-1}_k)\ge 3$. Note that $xv^{i-1}_{k+2}\notin E(G)$ by (P3). Let $z^*$ be the forth neighbor of $v^{i-1}_k$ if $d_{G_j}(v^{i-1}_k)=4$. If $v^i_{l-1}v^i_{l-2}\in E(G)$, then $z^*=v^i_{l-2}$ by (P3). By Claim 2, $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le |\mathcal {F}(v^i_l)|+3\le 6$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(2+1+6)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2.1.4 $q=1$, i.e., $v^i_lv^{i-1}_{k+1},v^i_lv^i_{l-1}\notin E(G)$.

Suppose that $v^{i-1}_k$ is the father of x. Let $z^*$ be the forth neighbor of $v^{i-1}_k$ if exists. Then $|\mathcal {F}(v^i_l)|\le |\{z^*,v^{i-2}_h,v^{i-1}_{k+1}\}|=3$. By Claim 2, $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le |\mathcal {F}(v^i_l)|+3\le 6$. Since $|C|-(q+2+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(1+2+6)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Suppose that $v^{i-1}_{k+1}$ is the father of x. Then $v^i_{l+1}v^{i-1}_{k+2}\notin E(G)$, and $|\mathcal {F}(v^i_l)|\le |(N(v^{i-1}_k)\setminus \{v^i_l\})\cup \{v^{i-1}_{k+1}\}|\le 4$. By Claim 2, $|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|\le |\mathcal {F}(v^i_l)|+3\le 7$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)\cup \mathcal {F}(x)|)\ge 10-(1+1+7)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Case 2.2 x is in layer $i+1$.

Then $xv^i_l$ has at most $q+1\le 4$ forbidden colors. If $d_G(x)=d_{G_j}(x)=1$, then we can legally color $xv^i_l$ with some color in C, because $|C|-(q+1+|\mathcal {F}(v^i_l)|)\ge 10-(q+1+5)\ge 1$ by Claim 1. Otherwise, $d_G(x)=d_{G_j}(x)=2$, i.e., $xv^i_l\in E(H)$, and $v^i_{l-1}$ is the father of x.

Case 2.2.1 $v^i_lv^{i-1}_{k+1}\in E(G)$.

Then $v^{i-1}_k$ is the father of $v^i_{l-1}$ by (P3), which implies that $d_{G_j}(v^{i-1}_k)\ge 3$. Let $z^*$ be the forth neighbor of $v^{i-1}_k$ if $d_{G_j}(v^{i-1}_k)=4$.

Suppose that $d_{G_j}(v^{i-1}_{k+1})=2$. Let $y^*$ be the neighbor of $v^{i-1}_{k+1}$ other than $v^i_l$. Then $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,y^*,v^i_{l-1}\}$. Moreover, when $q=3$, we have $v^i_lv^i_{l-1}\in E(G)$ and so $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,y^*\}$. Consequently, $q+|\mathcal {F}(v^i_l)|\le 6$. By Claim 3, $|\mathcal {F}(x)|\le 2$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(x)|)\ge 10-(6+1+2)=1$, we can legally color $xv^i_l$ with some color in C.

Suppose that $d_{G_j}(v^{i-1}_{k+1})\ge 3$. By the proof of Claim 3, $|\mathcal {F}(x)|\le 1$. By Claim 1, $|\mathcal {F}(v^i_l)|\le 5$. Moreover, if $q=3$, then $v^i_lv^i_{l-1}\in E(G)$ and $v^i_{l-1}\notin \mathcal {F}(v^i_l)$, implying $|\mathcal {F}(v^i_l)|\le 4$. Consequently, $q+|\mathcal {F}(v^i_l)|\le 7$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(x)|)\ge 10-(7+1+1)=1$, we can legally color $xv^i_l$ with some color in C.

Case 2.2.2 $v^i_lv^{i-1}_{k+1}\notin E(G)$.

Then $1\le q\le 2$. Assume that $q=1$. By Claim 1, $|\mathcal {F}(v^i_l)|\le 5$. By Claim 3, $|\mathcal {F}(x)|\le 2$. Since $|C|-(q+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(x)|)\ge 10-(1+1+5+2)=1$, we can legally color $xv^i_l$ with some color in C to get a 2DVDE partial coloring of G on $G_j$.

Assume that $q=2$, i.e., $v^i_lv^i_{l-1}\in E(G)$. We assert that $|C|-(q+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(x)|)\ge 1$, so that $xv^i_l$ can be legally colored with some color in C to get a 2DVDE partial coloring of G on $G_j$. Otherwise, we derive that $|\mathcal {F}(v^i_l)|=5$, $|\mathcal {F}(x)|=2$, and $\phi _{j-1}(xv^i_{l-1})\ne \phi _{j-1}(v^i_lv^{i-1}_{k})$. Hence $\phi _{j-1}(xv^i_{l-1})\notin \{\phi _{j-1}(v^i_lv^i_{l-1}),\phi _{j-1}(v^i_lv^{i-1}_{k})\}$, which implies that $v^{i-1}_k\notin \mathcal {F}(x)$. In view of the proof of Claim 3, we have $|\mathcal {F}(x)|\le 1$, a contradiction.

Case 3 $t=2$.

Then $q\le 2$. Let x and y be the neighbors of $v^i_l$ not in $G_{j-1}$. Note that at least one of x and y differs from $v^i_{l+1}$, say $y\ne v^i_{l+1}$. Our proof splits into the following two subcases.

Case 3.1 $x=v^{i}_{l+1}$.

Since $xv^i_l$ has at most $q+2\le 4$ forbidden colors, and $|\mathcal {F}(x)|\le 5$ by Claim 1, we can legally color $xv^i_l$ with a color a in C (at the moment, we do not consider whether or not $v^i_l$ has fully conflict vertices because $yv^i_l$ has not been colored). Now $yv^i_l$ still has at most $q+1+1\le 4$ forbidden colors.

If $d_G(y)>d_{G_j}(y)$, then we can legally color $yv^i_l$ with some color in C, because $|C|-(q+1+1+|\mathcal {F}(v^i_l)|)\ge 10-(q+2+5)\ge 1$ by Claim 1. Now assume that $d_G(y)=d_{G_j}(y)$. If $d_G(y)=d_{G_j}(y)=1$, then we can give $yv^i_l$ a legal coloring as in the previous case. Otherwise, $d_G(y)=d_{G_j}(y)=2$, i.e., $yv^i_l\in E(H)$. Then $v^i_{l-1}$ is the father of y.

Case 3.1.1 $v^{i-1}_{k+1}$ is the father of x.

Then $v^{i-1}_k$ is the father of $v^i_{l-1}$, and hence $d_{G_j}(v^{i-1}_k)\ge 3$. Let $z^*$ be the forth neighbor of $v^{i-1}_k$ if $d_{G_j}(v^{i-1}_k)=4$.

Suppose that $q=1$. Then $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,v^i_{l-1},v^{i-1}_{k+1}\}$ by Remark 1. By Claim 3, $|\mathcal {F}(y)|\le 2$. Since $|C|-(q+1+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(y)|)\ge 10-(1+1+1+4+2)=1$, we can legally color $yv^i_l$ with some color in C.

Suppose that $q=2$ and $v^i_lv^i_{l-1}\in E(G)$. If $v^i_{l-1}v^i_{l-2}\in E(G)$, then $z^*=v^i_{l-2}$ by (P3). So $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,v^{i-1}_{k+1}\}$ by Remark 1. By Claim 3, $|\mathcal {F}(y)|\le 2$. Since $|C|-(q+1+1+|\mathcal {F}(v^i_l)|+|\mathcal {F}(y)|)\ge 10-(2+1+1+3+2)=1$, we can legally color $yv^i_l$ with some color in C. If $v^i_{l-1}v^i_{l-2}\notin E(G)$, then we have a similar discussion.

Suppose that $q=2$ and $v^i_lv^{i-1}_{k+1}\in E(G)$. Then $d_{G_j}(v^{i-1}_{k+1})\ge 3$. Note that $v^{i-1}_{k+1}$ has at most two other neighbors, say $y_1,y_2$. Therefore, $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,v^i_{l-1},z^*,y_1,y_2\}$. By Claim 3, $|\mathcal {F}(y)|\le 2$. Without loss of generality, assume that $\phi _{j-1}(v^i_lv^{i-1}_k)=1$, $\phi _{j-1}(v^i_lv^{i-1}_{k+1})=2$, $a=3$, and $\phi _{j-1}(v^i_{l-1}y)=\alpha$.

• $\alpha \in \{1,2,3\}$. Suppose that $yv^i_l$ cannot be legally colored. It follows that $|\mathcal {F}(y)|=2$ and $|\mathcal {F}(v^i_l)|=5$. In this case, $x\in \mathcal {F}(y)$, and the second vertex in $\mathcal {F}(y)$ is $v^i_{l-2}$ or a neighbor of $v^i_{l-1}$ in layer $i+1$, say $u^*$, with $d_{G_j}(v^i_{l-2})=2$ or $d_{G_j}(u^*)=2$. If $v^i_{l-2}\in \mathcal {F}(y)$, then $v^i_{l-2}v^i_{l-1}\in E(H)$, and the father of $v^i_{l-2}$ is $v^{i-1}_k$ by (P3). That is $v^i_{l-2}\in \mathcal {F}(v^i_l)$. Hence, $|\mathcal {F}(y)\cup \mathcal {F}(v^i_l)|\le |\mathcal {F}(y)|+|\mathcal {F}(v^i_l)|-1=6$. Since $|C|-(q+1+|\mathcal {F}(y)\cup \mathcal {F}(v^i_l)|)\ge 10-(2+1+6)=1$, $yv^i_l$ can be legally colored, a contradiction. Next suppose that $u^*\in \mathcal {F}(y)$. Then the father of $u^*$ is $v^i_{l-2}$ by Lemma 1, and $v^{i-1}_k$ is the father of $v^i_{l-2}$ by (P3). That is $z^*=v^i_{l-2}$, which implies that $v^i_{l-2}=z^*\in \mathcal {F}(v^i_l)$. Without loss of generality, assume that $C_{\phi _{j-1}}(x)=\{3,4\}$, $C_{\phi _{j-1}}(y_i)=\{1,2,3,i+4\}$ for $i=1,2$, $C_{\phi _{j-1}}(v^{i-2}_h)=\{1,2,3,7\}$, $C_{\phi _{j-1}}(z^*)=\{1,2,3,8\}$, $C_{\phi _{j-1}}(v^i_{l-1})=\{1,2,3,9\}$, and $C_{\phi _{j-1}}(u^*)=\{\alpha ,10\}$. Then $10\in C_{\phi _{j-1}}(v^i_{l-1})$, which is impossible.

• $\alpha \notin \{1,2,3\}$, say $\alpha =4$. Then $x\notin \mathcal {F}(y)$, since when $yv^i_l$ is properly colored, x and y have different color sets. Similarly, we can show that $v^i_{l-1}\notin \mathcal {F}(v^i_l)$. Therefore $|\mathcal {F}(y)|\le 1$ and $|\mathcal {F}(v^i_l)|\le 4$ by the proof of Claims 1 and 3. Since $|C|-(4+|\mathcal {F}(y)|+|\mathcal {F}(v^i_l)|)\ge 10-(4+1+4)=1$, we can get a 2DVDE partial coloring of G on $G_j$.

Case 3.1.2 $v^{i-1}_k$ is the father of x.

Then $d_{G_j}(v^{i-1}_k)\ge 3$. Let $z^*$ be the forth neighbor of $v^{i-1}_k$ when $d_{G_j}(v^{i-1}_k)=4$.

If $xv^{i-1}_{k+1}\in E(G)$, then $z^*=v^i_{l-1}$, for else G contains a separating cycle with $v^{i-1}_k$ as an internal vertex, contradicting (P3). Hence, $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,v^{i-1}_{k+1}\}$. Since $|C|-(q+1+1+|\mathcal {F}(y)|+|\mathcal {F}(v^i_l)|)\ge 10-(2+1+1+2+3)=1$ by Claim 3, we can get a 2DVDE partial coloring of G on $G_j$. If $xv^{i-1}_{k+1}\notin E(G)$, then $\mathcal {F}(v^i_l)\subseteq \{v^{i-2}_h,z^*,v^{i}_{l-1}\}$ when $v^i_lv^i_{l-1}\notin E(G)$, or $\mathcal {F}(v^i_l)\cup \mathcal {F}(y)\subseteq \{v^{i-2}_h,z^*,z_1,z_2,x\}$ when $v^i_lv^i_{l-1}\in E(G)$, where $z_1,z_2$ denote the other two neighbors of $v^i_{l-1}$. Since $|C|-(q+1+1+|\mathcal {F}(y)|+|\mathcal {F}(v^i_l)|)\ge 10-(2+1+1+2+3)=1$ by Claim 3, we can get a 2DVDE partial coloring of G on $G_j$.

Case 3.2 $x\ne v^{i}_{l+1}$.

Both x and y are in layer $i+1$, say $x=v^{i+1}_{h}$, $y=v^{i+1}_{s}$ with $h>s$. Indeed, $h=s+1$ by Lemma 1. We first legally color $yv^i_l$ with some color $a\in C$, since $yv^i_l$ has at most $q+1\le 3$ forbidden colors, and $|\mathcal {F}(y)|\le 2$ by Claim 3. Then we color legally $xv^i_l$ with some color in $C\setminus \{a\}$, since $xv^i_l$ has at most $q+1\le 3$ forbidden colors, and $|\mathcal {F}(v^i_l)|\le 5$ by Claim 1.

Case 4 $t=3$.

Then $q=1$. Let $x_{1}, x_{2},x_{3}$ be the neighbors of $v^i_l$ not in $G_{j-1}$. Without loss of generality, we may assume that $x_{1}=v^{i}_{l+1}$, $x_{2}=v^{i+1}_s$, $x_3=v^{i+1}_{s+1}$ by Lemma 1. (If $x_1=v^{i+1}_{s-1}$, we have a similar discussion). First, since $x_{1}v^i_l$ has at most $q+2\le 3$ forbidden colors, and $|\mathcal {F}(x_1)|\le 5$ by Claim 1, we may legally color $x_{1}v^i_l$. Second, since $x_2v^i_l$ has at most $q+1\le 2$ forbidden colors and $|\mathcal {F}(x_2)|\le 2$ by Claim 3, we may legally color $x_2v^i_l$. Finally, since $|C|-(q+2)=7>|\mathcal {F}(v^i_l)|$, we color legally $x_3v^i_l$ with some color in C. $\square$

Using the result of Theorem 3, we now describe an algorithm of finding a 2DVDE 10-coloring in an outerplanar graph G with $\varDelta \le 4$:

Algorithm: 2DVDE-Color Outerplanar Graphs (II).

Input: A connected outerplanar graph G with maximum degree $\varDelta \le 4$;

Output: A 2DVDE 10-coloring of G;

• 1. Choose a $\varDelta$-vertex $u_1$ and run an OBFT partition starting from $u_1$.

• 2. Coloring $E(u_1)$ with colors $1, 2, \ldots , \varDelta$.

• 3. Coloring the edges in $G[\{u_2,u_3,\ldots ,u_{\varDelta +1}\}]$ with colors 5, 6, 7.

• 4. Coloring the uncolored edges in $E(u_j)$ for $j=2,3,\ldots ,\varDelta +1$ from left to right, where the used colors are selected as follows:

  • If j is even, the foregoing colors in the set $\{8, j, j+1, \ldots ,\varDelta , 1, 2, \ldots , j-2\}$ are used;

  • If j is odd, the foregoing colors in the set $\{9, j, j+1, \ldots ,\varDelta , 1, 2, \ldots , j-2\}$ are used.

• 5. Repeat for each vertex $u_j$ with $j\ge \varDelta +2$, from left to right, from top to down: Coloring the edges in $E(u_j)\setminus (E(u_1)\cup E(u_2)\cup \cdots \cup E(u_{j-1}))$ according to Theorem 3.

Similarly to the proof of Theorem 2, we obtain the following algorithmic complexity:

Theorem 4

Let G be a connected outerplanar graph with $n\ge 2$ vertices and $\varDelta \le 4$. The algorithm 2DVDE-Color Outerplanar Graphs (II) runs in $O(n^3)$ time.

4 Conclusion

In this paper, we focus on the study of 2-distance vertex-distinguishing index of the class of outerplanar graphs. Combining Theorems 1 and 3, we have the following consequence:

Theorem 5

If G is an outerplane graph, then $\chi '_{d2}(G)\le \varDelta +8$.

The upper bound $\varDelta +8$ in Theorem 5 seems not to be best possible. We like to conclude this paper by raising the following conjecture:

Conjecture 3

If G is an outerplane graph, then $\chi '_{d2}(G)\le \varDelta +2$.

Note that if a graph G contains two $\varDelta$-vertices at distance 2, then $\chi '_{d2}(G)\ge \varDelta +1$. On the other hand, it is easy to construct infinitely many outerplanar graphs G with $\chi '_{d2}(G)=\varDelta +1$. These two facts imply that the upper bound $\varDelta +1$ is tight, if Conjecture 3 is true.