Electronic Journal of Graph Theory and Applications

Mahsa Mozafari-Nia^a, Moharram N. Iradmusa**ab

^aDepartment of Mathematical Sciences, Shahid Beheshti University, G.C.,

P.O. Box 19839-63113, Tehran, Iran.

^bSchool of Mathematics, Institute for Research in Fundamental Sciences (IPM),

P.O. Box: 19395-5746, Tehran, Iran.

mahsamozafary@gmail.com, m_iradmusa@sbu.ac.ir

A vi-simultaneous proper k-coloring of a graph G is a coloring of all vertices and incidences of the graph in which any two adjacent or incident elements in the set \(V(G) \cup I(G)\) receive distinct colors, where I(G) is the set of incidences of G. The vi-simultaneous chromatic number, denoted by \(\chi_{vi}(G)\), is the smallest integer k such that G has a vi-simultaneous proper k-coloring. In [M. Mozafari-Nia, M. N. Iradmusa, A note on coloring of \(\frac{3}{3}\)-power of subquartic graphs, Vol. 79, No.3, 2021] vi-simultaneous proper coloring of graphs with maximum degree 4 is investigated and they conjectured that for any graph G with maximum degree \(\Delta \geq 2\), vi-simultaneous proper coloring of G is at most \(2\Delta + 1\). In [M. Mozafari-Nia, M. N. Iradmusa, Simultaneous coloring of vertices and incidences of graphs, arXiv:2205.07189, 2022] the correctness of the conjecture for some classes of graphs such as k-degenerated graphs, cycles, forests, complete graphs, regular bipartite graphs is investigated. In this paper, we prove that the vi-simultaneous chromatic number of any outerplanar graph G is either \(\Delta + 2\) or \(\Delta + 3\), where \(\Delta\) is the maximum degree of G.

Keywords: incidence of graph, simultaneous coloring of graph, outerplanar graph

Mathematics Subject Classification: 05C15, 05C10

DOI: 10.5614/ejgta.2023.11.1.20

Received: 3 June 2022, Revised: 11 October 2022, Accepted: 6 January 2023.

^*corresponding author

1. Introduction

All graphs we consider in this paper are simple, finite and undirected. For a graph G, we denote its vertex set, edge set, face set (if G is planar), maximum degree and maximum size of cliques of G by V(G), E(G), F(G), \(\Delta(G)\) and \(\omega(G)\), respectively. Also, for a vertex \(v \in V(G)\), \(N_G(v)\) is the set of neighbors of v in G and any vertex of degree k is called a k-vertex. From now on, we use the notation [n] instead of \(\{1,\ldots,n\}\). We mention some of the definitions that are referred to throughout the note and for other necessary definitions and notations, we refer the reader to a standard text-book [3].

For any graph G, apart from vertices and edges of the graph as its elements, we have incidences of G as other elements of the graph. The concepts of incidences of a graph were introduced by Brualdi and Massey in 1993 [7]. In graph G, any pair i=(v,e) is called an incidence of G, if \(v \in V(G)\), \(e \in E(G)\) and \(v \in e\). In this case, the elements v and i are called incident. When u and v are adjacent vertices, we use the notation (u,v) instead of \((u,\{u,v\})\) in the figures and the proofs for simplicity. The set of the incidences of G is denoted by I(G).

Definition 1.1. [7] Let G = (V, E) be a multigraph. The incidence graph of G, denoted by \(\mathcal{I}(G)\), defined with vertex set I(G) and with an edge between any pair of incidences (v, e) and (w, f) provided one of the following holds:

• (1) v = w,
• (2) e = f,
• (3) the edge \(\{v, w\}\) equals e or f.

For any edge \(e = \{u, v\}\), we call (u, e), the first incidence of u and (v, e), the second incidence of u. In general, for a vertex \(v \in V(G)\), the set of the first incidences and the second incidences of v is denoted by \(I_1^G(v)\) and \(I_2^G(v)\), respectively. Also, let \(I_G(v) = I_1^G(v) \cup I_2^G(v)\), \(I_G[v] = \{v\} \cup I_G(v)\), \(I_1^G[v] = \{v\} \cup I_1^G(v)\) and \(I_2^G[v] = \{v\} \cup I_2^G(v)\). Sometime we remove the index G for simplicity.

A mapping c from V(G) to [k] is a proper k-coloring of G, if \(c(v) \neq c(u)\) for any two adjacent vertices u and v. A minimum integer k that G has a proper k-coloring is the chromatic number of G and denoted by \(\chi(G)\).

Instead of the vertices, we can color the edges or the incidences of a graph. A mapping c from E(G) to [k] is a proper edge-k-coloring of G, if \(c(e) \neq c(e')\) for any two adjacent edges e and e' \((e \cap e' \neq \varnothing)\). A minimum integer k that G has a proper edge-k-coloring is the chromatic index of G and denoted by \(\chi'(G)\). Similarly, any proper k-coloring of \(\mathcal{I}(G)\) is an incidence k-coloring of G. The incidence chromatic number of G, denoted by \(\chi_i(G)\), is the minimum integer k such that G is incidence k-colorable

Another coloring of a graph is simultaneous coloring in which we color two or three kinds of elements of the graph at the same time subject to some constraints. The first and the most well-known simultaneous coloring of graphs is total coloring which was introduced by Behzad in 1965 [2]. A mapping c from \(V(G) \cup E(G)\) to [k] is a proper total k-coloring of G, if \(c(x) \neq c(y)\) for any two adjacent or incident elements x and y. A minimum integer k that G has a proper total k-coloring is the total chromatic number of G and denoted by \(\chi''(G)\). Behzad conjectured that \(\chi''(G)\) never exceeds \(\Delta(G) + 2\).

There are some other types of simultaneous coloring in which we color at least two sets of the sets V(G), E(G), and F(G) in the coloring [5, 8, 17, 21, 22]. Ringel conjectured [17] that six colors are enough for simultaneous coloring of the vertices and faces of each plane graph G, i.e., \(\chi_{vf}(G) \leq 6\), and proved \(\chi_{vf}(G) \leq 7\). This conjecture was proved later in [6]. Kronk and Mitchem conjectured that \(\Delta(G)+4\) colors are enough for entire coloring of the vertices, edges and faces of each plane graph G, i.e., \(\chi_{vef}(G) \leq \Delta(G)+4\) and confirmed the conjecture for the case \(\Delta(G) \leq 3\) [12]. The conjecture was proved in [4] for \(\Delta(G) \geq 7\), in [18] for \(\Delta(G) = 6\), in [22] for \(4 \leq \Delta(G) \leq 5\). Simultaneous coloring the edges and faces of 3- and 4-regular planar graphs has been considered by Jucovic [11] and Fiamcik [9]. Melnikov ([10], page 543) conjectured that \(\chi_{ef}(G) \leq \Delta(G) + 3\) for any planar graph G. This conjecture was proved in [5] for \(\Delta(G) \geq 10\). Precisely, Borodin proved that \(\chi_{ef}(G) \leq \Delta(G) + 1\) for each planar graph with \(\Delta(G) \geq 10\). Finally, this conjecture was proved by Adrian Waller for any planar graph [19].

In this paper, we are going to investigate the simultaneous coloring of the vertices and the incidences of a graph which is defined in the following.

Definition 1.2. [15] Let G be a graph. A vi-simultaneous proper k-coloring of G is a coloring \(c: V(G) \cup I(G) \longrightarrow [k]\) in which any two adjacent or incident elements in the set \(V(G) \cup I(G)\) receive distinct colors. Precisely, \(c(x) \neq c(y)\) if one of the following holds:

• (1) x and y are adjacent vertices of G,
• (2) x and y are adjacent vertices of \(\mathcal{I}(G)\),
• (3) x and y are incident, where \(x \in V(G)\) and \(y \in I(G)\) or \(x \in I(G)\) and \(y \in V(G)\).

The vi-simultaneous chromatic number, denoted by \(\chi_{vi}(G)\), is the smallest integer k such that G has a vi-simultaneous proper k-coloring.

For example, in Figure 1, a vi-simultaneous proper 5-coloring of the graph G is shown. Note that in the figures, black vertices are corresponding to the vertices of G and white vertices are corresponding to the incidences of G.

The relation between vi-simultaneous coloring of a graph and vertex coloring of its \(\frac{3}{3}\) power was shown in [15]. The fractional power of graphs was introduced by the second author in [13]. By considering an arbitrary graph G and positive integer n, we can construct two different graphs, named n-power of G, denoted by \(G^n\), which is constructed by adding an edge between any two vertices of G with distance at most n, and n-subdivision of G, denoted by \(G^{\frac{1}{n}}\), which is constructed by replacing each edge \(\{x,y\}\) of G with a path of length n, including vertices \(x=(xy)_0, (xy)_1, \ldots, (xy)_{n-1}\) and \(y=(xy)_n\). The vertices \((xy)_0\) and \((xy)_n\) are called terminal vertices and the others are called internal vertices. We refer to these vertices in short, t-vertices and i-vertices of G, respectively. To avoid ambiguity, we emphasize that these two notations do not mean the vertices of degree t or i. Now, the \(\frac{m}{n}\)-fractional power of a graph G is defined to be the m-power of the n-subdivision of G. In other words, \(G^{\frac{m}{n}} = (G^{\frac{1}{n}})^m\). In [15], it is proved that for any graph G, \(\chi_{vi}(G) = \chi(G^{\frac{3}{3}})\).

Let G be a graph with \(\Delta(G) = \Delta\). We need at least \(\Delta + 2\) colors for any vi-simultaneous proper coloring of G. Suppose that v is a \(\Delta\)-vertex in G and \(u \in N_G(v)\). Since any two elements of \(I_1^G[v] \cup \{(u,v)\}\) are adjacent or incident, \(\chi_{vi}(G) \geq \Delta(G) + 2\). Therefore, the problem of finding

Figure 1: (Right) Black vertices are corresponding to the vertices of G and white vertices are corresponding to the incidences of G. The incidence (u, {u, v}) is denoted by (u, v). (Left) vi-simultaneous proper 5-coloring of graph G.

some upper bounds for vi-simultaneous chromatic number of graph G in terms of ∆(G) is a natural problem.

We can define some special kind of vi-simultaneous coloring of graphs by restricting the number of colors that appear on the incidences of each vertex.

Definition 1.3. [15] A vi-simultaneous proper k-coloring of a graph G is called vi-simultaneous (k, s)-coloring of G if for any vertex v, the number of colors used for coloring I2(v) is at most s. We denote by χvi,s(G) the smallest number of colors required for a vi-simultaneous (k, s)-coloring of G.

As you can see in Figure 1, the given coloring for the graph is a vi-simultaneous (5, 1)-coloring. Obviously, one can show that χvi,1(G) ≥ χvi,2(G) ≥ χvi,3(G) ≥ · · · ≥ χvi,∆(G) = χvi(G) for any graph G with ∆(G) = ∆. For example χvi,1(K3) = 6 > χvi,2(K3) = χvi(K3) = 5 (see Figure 2).

Figure 2: (Left) vi-simultaneous proper (6, 1)-coloring of K3. (Right) vi-simultaneous proper (5, 2)-coloring of K3.

In [14, 15], vi-simultaneous proper coloring of graphs is investigated. In [14], it is proved that χvi(G) ≤ 9 for any graph G with ∆(G) ≤ 4. Also, the following conjecture was proposed:

Conjecture 1. [14] Let G be a graph with ∆(G) ≥ 2. Then χvi(G) ≤ 2∆(G) + 1.

The correctness of the conjecture is proved for some classes of graphs in [15]. In this paper, we are going to find the upper bounds for the vi-simultaneous chromatic number of outerplanar graphs and investigate the correctness of the conjecture for these graphs. The main theorems are as follows.

Theorem 1.1. If G is an outerplanar graph, then \(\chi_{vi,2}(G) \leq \Delta(G) + 3\).

Theorem 1.2. Suppose that G is an outerplanar graph. Then

\[\chi_{vi,1}(G) \leq \begin{cases} \Delta + 3, & g(G) \geq 4, \\ \Delta + 2, & \Delta(G) \geq 4 \text{ and } g(G) \geq 6, \\ \Delta + 2, & \Delta(G) \geq 5 \text{ and } g(G) \geq 4. \end{cases}\]

Note that, since \(\chi_{vi,1}(G) \geq \Delta + 2\), in the last two cases, we have \(\chi_{vi,1}(G) = \Delta + 2\).

The paper is organized as follows. In Section 2, some preliminary definitions and theorems are mentioned and Section 3 is devoted to the proofs of the main theorems.

2. Preliminaries and Definitions

To prove theorems expressed in Section 3, we need some definitions and theorems which are stated in [13, 15]. As we mentioned before, the vi-simultaneous coloring of some classes of graphs are investigated in [15]. Some of these results we are going to use are as follows.

Theorem 2.1. [13] Let \(m, n \in \mathbb{N}\) and \(k \geq 3\).

• \[\chi(C_k^m) = \begin{cases} k, & m \ge \lfloor \frac{k}{2} \rfloor, \\ \lceil \frac{k}{\lfloor \frac{k}{m+1} \rfloor} \rceil, & m < \lfloor \frac{k}{2} \rfloor. \end{cases}\]

\[\bullet \ \chi(P_k^m) = \min\{m+1,k\}\]

By Theorem 2.1 and the fact that \(C_n^{\frac{3}{3}} = C_{3n}^3\) and \(P_n^{\frac{3}{3}} = P_{3n-2}^3\), we have the following corollary.

Corollary 2.1. If G is a cycle of length n, then \(\chi_{vi}(C_n) = \chi(C_n^{\frac{3}{3}}) = 4\), when \(n \equiv 0 \pmod{4}\). Otherwise, \(\chi_{vi}(C_n) = \chi(C_n^{\frac{3}{3}}) = 5\). Moreover, for any path \(P_n\), we have \(\chi_{vi}(P_n) = \chi(P_n^{\frac{3}{3}}) = 4\).

Theorem 2.2. [15] Let \(3 < n \in \mathbb{N}\). Then

\[\chi_{vi,1}(C_n) = \begin{cases} 6, & n = 3, \\ 4, & n \equiv 0 \pmod{4}, \\ 5, & otherwise. \end{cases}\]

Theorem 2.3. [15] Let F be a forest. Then

\[\chi_{vi,1}(F) = \begin{cases} 1, & \Delta(F) = 0, \\ 4, & \Delta(F) = 1, \\ \Delta(F) + 2, & \Delta(F) \ge 2. \end{cases}\]

Theorem 2.4. [15] χvi(Kn) = n + 2 for each n ∈ N \ {1}.

A graph G is a k-degenerated graph if any subgraph of G contains a vertex of degree at most k.

Theorem 2.5. [15] Let k ∈ N and G be a k-degenerated graph with ∆(G) ≥ 2. Then χvi,k(G) ≤ ∆(G) + 2k.

Theorem 2.6. [15] Let G be a graph with maximum degree ∆ and c is a vi-simultaneous proper (∆ + 2)-coloring of G with colors from [∆ + 2]. Then |c(I2(v))| ≤ ∆ − dG(v) + 1 for any vertex v ∈ V (G), where c(I2(v)) = {c(x) | x ∈ I2(v)} . Specially |c(I2(v))| = 1 for any ∆-vertex v of G.

Theorem 2.7. [15] Let G be a graph, e be a cut edge of G and C¹ and C² be two components of G − e. Then χvi,l(G) = max{χvi,l(H1), χvi,l(H2)} where Hⁱ = Cⁱ + e for i ∈ {1, 2} and 1 ≤ l ≤ ∆(G).

Theorem 2.8. [15] Let G¹ and G² be two graphs, V (G1)∩V (G2) = {v} and G = G¹ ∪G2. Then

\[\chi_{vi,1}(G) = \max\{\chi_{vi,1}(G_1), \chi_{vi,1}(G_2), \deg_G(v) + 2\}.\]

Corollary 2.2. Let k ∈ N and G be a graph with blocks B1, . . . , Bk. Then

\[\chi_{vi,1}(G) = \max\{\chi_{vi,1}(B_1), \dots, \chi_{vi,1}(B_k), \deg_G(v_1) + 2, \dots, \deg_G(v_s) + 2\},\\]

where v1, . . . , v^s are the cut vertices of the graph G.

In [15], it is shown that there is a relationship between vi-simultaneous coloring of graphs and two parameters χ ′′(G) and st(G), where st(G) is the star arboricity of the graph G which was introduced by Algor and Alon [1]. The star arboricity of a graph is the minimum number of star forests (forests whose connected components are stars) in G whose union covers all edges of G.

Theorem 2.9. [15] For any graph G, we have χvi(G) ≤ χ ′′(G) + st(G).

Theorem 2.10. [15] χvi,1(G) ≤ max{χ(G² ), χl(G) + ∆(G) + 1} for any nonempty graph G. Specially, if χ(G² ) ≥ χl(G) + ∆(G) + 1, then χvi,1(G) = χ(G² ).

3. Main Theorems

In this section, we investigate the vi-simultaneous chromatic number of outerplanar graphs with defined maximum degree and girth. A graph is said to be planar, if it can be drawn in the plane so that its edges intersect only at their ends. An outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing and in a 2-conneced outerplanar graph, the outer face is a Hamiltonian cycle. The girth of a graph G, denoted by g(G), is the length of a shortest cycle in G. A block of the graph G is a maximal 2-connected subgraph of G and if G is 2-connected, then G itself is called a block. Also, an end block of G is a block

with a single cut vertex. We know that each connected graph with at least one cut vertex has at least two end blocks. For more information about blocks, see Chapter 5, the Section 5.2 of [3].

A face f ∈ F(G) with degree k is denoted by its boundary walk f = [v1v² . . . vk], where v1, v2, . . . , v^k are its vertices in the clockwise order. We say that a face f = [v1v² . . . vk] is an end face of an outerplane graph G, if v2, . . . , vk−¹ are all 2-vertices in G. For more information about the outerplanar graph, see Capther 6, the Section 6.1 of [23].

We know that any outerplanar graph is a 2-degenerated graph. So by use of Theorem 2.5 we can achieve the following upper bound for χvi,2(G).

Proposition 3.1. If G is an outerplanar graph with maximum degree ∆, then χvi,2(G) ≤ ∆ + 4.

As stated in Theorem 1.1, we improve this upper bound to ∆(G)+3 but we need the Proposition 3.1 in the proof. The following lemma easily follows from Proposition 6.1.20 in [23] which states that every simple outerplanar graph has a vertex of degree at most two.

Lemma 3.1. For any nonempty outerplanar graph G at least one of the following holds:

• (i) G has a 1-vertex,
• (ii) G has two adjacent 2-vertices,
• (iii) G has a 2-vertex with adjacent neighbors.

Especially, any 2-connected outerplanar graph of order at least three has no 1-vertex and so holds in (ii) or (iii).

3.1. Proof of the Theorem 1.1

In order to prove of the Theorem 1.1, first we are going to prove it for 2-connected outerplanar graphs with maximum degree at least 3. Before we get into that, it should be noted that by Corollary 2.1, Theorem 1.1 is true for all outerplanar graphs with maximum degree at most two.

A graph G is called subcubic, if ∆(G) ≤ 3. Also, a 3-regular graph is called a cubic graph.

Theorem 3.1. If G is a 2-connected outerplanar graph with ∆(G) = 3, then χvi,2(G) ≤ 6. Moreover, the bound is tight.

Proof. We prove the theorem by induction on the order of G. There is only one 2-connected outerplanar graphs of order 4 with ∆(G) = 3 which is vi-simultaneous (6, 1)-colorable (See Figure 3). Easily one can show that 6 colors are necessary for this graph. Now suppose that G is a 2-connected outerplanar graph of order n ≥ 5 with ∆(G) = 3, and the statement is true for all 2 connected outerplanar graphs with maximum degree 3 of order less than n. Since G is 2-connected and ∆(G) = 3, G has an end face f = [vivi+1 . . . v^j ] of degree at least 3.

First, suppose that f = [vivi+1vi+2] and G′ = G − vi+1. If ∆(G′ ) = 2, then by use of Theorem 2.2, G′ has a proper vi-simultaneous (5, 1)-coloring, named c with colors in [5]. If ∆(G′ ) = 3, then by the induction hypothesis, G′ has a proper vi-simultaneous (6, 2)-coloring c with colors in [6]. Now, it suffices to extend c to a proper vi-simultaneous (6, 2)-coloring for G.

Since vⁱ , vi+2, (vⁱ , vi+2) and (vi+2, vi) are pairwise adjacent in (G′ ) ³ , they must have different colors. Without loss of generality, suppose that c(vi) = 1, c((vⁱ , vi+2)) = 2, c((vi+2, vi)) = 3 and c(vi+2) = 4. If the color 1 is available for the i-vertex (vi+2, vi+1) or the color 4 is available for the

Figure 3: vi-simultaneous (6, 1)-coloring 2-connected outerplanar graph of order four.

i-vertex \((v_i, v_{i+1})\), then with a simple review c can be extended to a (6,2)-proper coloring c' for \(G^{\frac{3}{3}}\). In addition, if \(c((v_{i-1}, v_i)) = 4\), then color 4 is available for \((v_{i+1}, v_i)\) and if \(c((v_{i+3}, v_{i+2})) = 1\), then color 1 is available for \((v_{i+1}, v_{i+2})\) and again in each of these cases, c can be extended to a (6,2)-proper coloring c' for \(G^{\frac{3}{3}}\). Otherwise, the i-vertices \((v_i, v_{i-1})\) and \((v_{i+2}, v_{i+3})\) must have colors 4 and 1, respectively. If at least one of colors 5 or 6 is available for both i-vertices \((v_i, v_{i+1})\) and \((v_{i+2}, v_{i+1})\), then color them with the available color from \(\{5,6\}\). Also, assign colors 2 and 3 to i-vertices \((v_{i+1}, v_{i+2})\) and \((v_{i+1}, v_i)\), respectively and color \(v_{i+1}\) with the remaining color from \(\{5,6\}\). Otherwise, the i-vertices \((v_{i-1}, v_i)\) and \((v_{i+3}, v_{i+2})\) must have colors 5 and 6. Without loss of generality, let \(c((v_{i-1}, v_i)) = 5\) and \(c((v_{i+3}, v_{i+2})) = 6\). Now we change the color of \((v_i, v_{i+2})\) to 6 and then we use color 2 for the i-vertices \((v_i, v_{i+1})\) and \((v_{i+2}, v_{i+1})\), color 3 for \((v_{i+1}, v_i)\), color 6 for \((v_{i+1}, v_{i+2})\) and color 5 for \(v_{i+1}\). Easily the extended coloring is a \(v_i\)-simultaneous (6,2)-coloring for G.

Now suppose that \(f = [v_i v_{i+1} v_{i+2} v_{i+3}]\). There are at least one available color for i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+2})\). In addition, we color vertices \((v_{i+1}, v_i)\) and \(v_{i+2}\) with color 3, the vertices \(v_{i+1}\) and \((v_{i+2}, v_{i+3})\) with color 2, the vertex \((v_{i+1}, v_{i+2})\) with color 1 and the vertex \((v_{i+2}, v_{i+1})\) with color 4. Easily one can show that, this coloring is a \(v_i\)-simultaneous (6, 2)-coloring for G.

If \(f = [v_i v_{i+1} v_{i+2} \dots v_j]\) and \(j \ge i+4\), then we consider the graph G' = G+e where \(e = \{v_{i+1}, v_{i+3}\}\) and similar to the first case, we prove that \(\chi_{vi,2}(G') \le 6\) which concludes that \(\chi_{vi,2}(G) \le 6\).

Theorem 3.2. For any outerplanar graph G with maximum degree 3, \(\chi_{vi,2}(G) \leq 6\).

Proof. We prove the theorem by the induction on the number of blocks. According to Theorem 3.1, the claim is true for blocks. Now suppose that \(k \in \mathbb{N} \setminus \{1\}\) and G is an outerplanar graph with \(\Delta(G) = 3\) and k blocks and the statement is true for all outerplanar graphs with \(\Delta = 3\) and less than k blocks. Since \(\Delta(G) = 3\), from any two blocks with a common cut vertex, one block must be \(K_2\). So G has at least one cut edge such as \(e = \{u, v\}\). If \(d_G(u) \neq 1 \neq d_G(v)\), then by use of Theorem 2.7, the theorem follows by induction applied to \(C_1 + e\) and \(C_2 + e\) where \(C_1\) and \(C_2\) are the components of G - e. Now suppose that \(d_G(u) = 1 < d_G(v)\). In this case, the graph

G − u is an outerplanar graph with k − 1 blocks. Hence, by induction hypothesis, G − u has a visimultaneous (6, 2)-coloring, named c, with color set [6]. Suppose that NG(v) = {v1, v2, u}. Now, color i-vertices (v, u) with one color from [6] \ {c(v), c((v, v1)), c((v1, v)), c((v, v2)), c((v2, v))}, then color the i-vertex (u, v) with the color c((v1, v)) or c((v2, v)) and finally color the vertex u with one available color from [6] \ {c(v), c((v, u)), c((u, v))}. The given coloring is a vi-simultaneous (6, 2)-coloring for G.

Theorem 3.3. For any outerplanar graph G with ∆(G) = ∆ ≥ 4, χvi,2(G) ≤ ∆ + 3.

Figure 4: Five outerplanar graphs of order 5 with maximum degree 4. Uncolored graphs are subgraphs of the colored graph.

Proof. We prove the theorem by induction on the order of G. Since ∆(G) ≥ 4, G has at least five vertices. There are five outerplanar graphs of order five with maximum degree at least 4 (Figure 4). Since all of them are subgraphs of the first graph G1, we need only to find a vi-simultaneous (7, 2)-coloring for G1. A vi-simultaneous (6, 1)-coloring of G¹ is shown in Figure 4. Now suppose that the theorem is true for all outerplanar graphs of order less than n and let G be an outerplanar graph of order n with ∆ ≥ 4. There are three cases, corresponding to the cases in Lemma 3.1.

• (i) Let dG(v) = 1 and u be the vertex adjacent to v. Then G′ = G − v is an outerplanar graph of smaller order and maximum degree at most ∆. If ∆(G) = 4 and ∆(G′ ) = ∆(G) − 1 = 3 then by use of Theorem 3.1 and otherwise, by the induction hypothesis, G′ has a vi-simultaneous (∆ + 3, 2)-coloring named c. We extend c to a vi-simultaneous (∆ + 3, 2)-coloring of G. The degree of u in G′ is at most ∆ − 1, so there are at most ∆ + 2 colors used by the vertices of I[u]. Hence, there is at least one color left to color the i-vertex (u, v). Also, the i-vertex (v, u) can be colored by one color of c(I2(u)). Finally, there are at least ∆ available colors for coloring v.
• (ii) G has two adjacent 2-vertices v and u. Let x be the vertex adjacent to v and y be the vertex adjacent to u. Consider G′ = G − {v, u}. Again, G′ is outerplanar with smaller order and maximum degree at most ∆ and so by use of Theorem 3.1 or the induction hypothesis, G has a

vi-simultaneous \((\Delta+3,2)\)-coloring named c. We extend c to a vi-simultaneous \((\Delta+3,2)\)-coloring of G. The degree of x and y in G' is at most \(\Delta-1\), so similar to the previous case, there is at least one color left to color each of the i-vertices (x,v) and (y,u). Also, each of the i-vertices (v,x) and (u,y) can be colored by one color of \(c(I_2^{G'}(x))\) and \(c(I_2^{G'}(y))\), respectively. After coloring these vertices, there are at least \(\Delta\) available colors for the coloring \(\{v,(v,u),(u,v),u\}\). Since \(\Delta \geq 4\), we can color properly the remain vertices.

(iii) G has a 2-vertex v with adjacent neighbors u and w. Consider G' = G - v. Again, G' is outerplanar with smaller order and maximum degree at most \(\Delta\) and so has a vi-simultaneous \((\Delta + 3, 2)\)-coloring named c. Suppose (u, w) is colored by color r and (w, u) by color s. We now assign color r to (v, w) and color s to (v, u). This does not produce any conflict. The degree of u and w in G' is at most \(\Delta - 1\), so similar to the previous cases, there is at least one color left to color each of the i-vertices (u, v) and (w, v). After coloring these vertices, there are at least \(\Delta - 3\) available colors for the coloring v. Since \(\Delta \geq 4\), we can complete the coloring. \(\square\)

Corollary 3.1. \(\chi_{vi}(G) \leq \Delta(G) + 3\) for any outerplanar graph G.

Due to the previous corollary, the Conjecture 1 is true for all outerplanar graphs. Also, Corollary 3.1 implies that the vi-simultanious chromatic number of any outerplanar graph G is equal to either \(\Delta(G)+2\) or \(\Delta(G)+3\). Those outerplanar graphs G for which \(\chi_{vi}(G)=\Delta(G)+2\) are said to belong to vi-class one, and the others to vi-class two. The vi-class number of graph is defined as follows.

Definition 3.1. Let G be a nonempty graph with vi-simultanious chromatic number equal to \(\Delta(G) + 1 + s\), where \(s \in \mathbb{N}\). We say that G is a graph of vi-class s.

For example, Theorem 2.4 shows that all complete graphs are of vi-class 2 and Theorem 2.3, shows that any forest with maximum degree at least 2 is a graph of vi-class 1.

In [20], the authors posed this question: Is there any graph G with \(\Delta(G)=3\) such that \(\chi(G^{\frac{3}{3}})=6\)? In fact, the question is about the existence of subcubic graphs of vi-class 2 or 3. In the next theorem, we show that the upper bound of Theorems 3.2 and 3.1 are tight and there are infinite subcubic graphs of vi-class two (with vi-simultaneous chromatic number 6).

Theorem 3.4. Any graph that contains at least one of the following subgraphs (Figure 5) is not vi-simultaneous 5-colorable. Especially, for any outerplanar cubic graph G that contains at least one of these subgraphs, \(\chi_{vi}(G) = 6\).

Proof. Let s be a vi-simultanious 5-coloring of \(G_i\) (\(1 \le i \le 4\)). We have following cases.

• \((G_1)\) Theorem 2.6 implies that s((b,a)) = s((c,a)) = s((d,a)) and s((a,b)) = s((c,b)) = s((d,b)). Each color class of s has at most 3 vertices. In addition, each color class that contains the color s(a) or s(b) has at most 2 vertices. Therefore, 5 colors are not enough and \(\chi_{vi}(G) \ge 6\).

Figure 5: Four subgraphs of Theorem 3.4.

• (G2) Theorem 2.6 implies that s((b, a)) = s((c, a)) = s((e, a)), s((a, b)) = s((c, b)) = s((f, b)) and s((a, c)) = s((b, c)) = s((d, c)). In addition,

\[|\{s(a), s(b), s(c)\}| = |\{s((a,b)), s((b,a)), s((a,c))\}| = 3\]

and \[\{s(a), s(b), s(c)\} \cap \{s((a,b)), s((b,a)), s((a,c))\} = \emptyset\]. So \(\chi_{vi}(G) \ge 6\).

• (G3) Without loss of generality, suppose that s(b) = 1, s((b, c)) = 2, s((b, a)) = 3 and s((b, e)) = 4. Theorem 2.6 implies that s((c, b)) = s((a, b)) = s((e, b)), s((c, a)) = s((b, a)) = s((d, a)) = 3 and s((b, e)) = s((d, e)) = s((f, e)) = 4. Suppose that s((c, b)) = s((a, b)) = s((e, b)) = 5. Since c is a vi-simultanious 5-coloring, s(c) = 4. Consecutively we have s(a) = 2 and then s((a, c)) = 1. Now we have no choice for the color of (a, d), a contradiction. So χvi(G) ≥ 6.
• (G4) Without loss of generality, suppose that s(b) = 1, s((b, c)) = 2, s((b, a)) = 3 and s((b, e)) = 4. Theorem 2.6 implies that s((c, b)) = s((a, b)) = s((e, b)), s((c, a)) = s((b, a)) = s((d, a)) = 3, s((b, e)) = s((f, e)) = s((k, e)) = 4 and s((a, d)) = s((f, d)) = s((h, d)). Suppose that s((c, b)) = s((a, b)) = s((e, b)) = 5. Since c is a vi-simultanious 5-coloring, s(c) = 4. Consecutively we have s(a) = 2 and then s((a, c)) = 1. Since s((f, d)) ̸= s((f, e)) = 4, s((a, d)) ̸= 4. Now we have no choice for the color of (a, d), a contradiction. So χvi(G) ≥ 6.

3.2. Proof of the Theorem 1.2

Given the fact that χvi,1(K2) = 4 and by use of Corollary 2.2, we only need to prove the Theorem 1.2 for 2-connected outerplanar graphs with the desired properties. According to Theorem 2.2, we suppose that ∆(G) ≥ 3. We prove the first case (when g(G) ≥ 4) in Theorems 3.5 and 3.6, the second case (when ∆(G) ≥ 4 and g(G) ≥ 6) in Theorem 3.8 and the third case (when ∆(G) ≥ 5 and g(G) ≥ 4) in Theorem 3.10.

Theorem 3.5. If G is a 2-connected outerplanar graph with \(\Delta(G) = 3\) and \(g(G) \geq 4\), then \(\chi_{vi,1}(G) \leq 6\).

Proof. Suppose that \(\Delta(G)=\Delta\) and g(G)=g. We prove the theorem by induction on the order of G. Since G is 2-connected, \(\Delta\geq 3\) and \(g\geq 4\), G has at least six vertices. In Figure 6, the only 2-connected outerplanar graph of order 6 with \(\Delta=3\) and g=4 with a vi-simultanious (6,1)-coloring is shown. Now suppose that G is a 2-connected outerplanar graph of order n with \(\Delta=3\)

Figure 6: 2-connected outerplanar graph G of order 6 with \(\Delta(G) = 3\) and g(G) = 4.

and g=4, and the statement is true for all 2-connected outerplanar graphs of order less than n with \(\Delta=3\) and g=4. Since G is 2-connected, G has an end face \(f=[v_iv_{i+1}\dots v_j]\) of degree at least 4. Let S be the set of 2-vertices of f and G'=G-S.

First, suppose that \(f = [v_i v_{i+1} v_{i+2} v_{i+3}]\). If \(\Delta(G') = 2\), then by Lemma 2.2, G' has a vi-simultaneous (5,1)-coloring c and if \(\Delta(G') = 3\), then by induction hypothesis G' has a vi-simultaneous (6,1)-coloring such as c. Now, it suffices to extend c to a proper vi-simultaneous (6,1)-coloring for G.

Since \(v_i\), \(v_{i+3}\), \((v_i, v_{i+3})\) and \((v_{i+3}, v_i)\) are pairwise adjacent in \((G')^{\frac{3}{3}}\), they must have different colors. Without loss of generality, suppose that \(c(v_i) = 1\), \(c((v_i, v_{i+3})) = 2\), \(c((v_{i+3}, v_i)) = 3\) and \(c(v_{i+3}) = 4\). Note that, by coloring of \((G')^{\frac{3}{3}}\), we have \(c((v_{i-1}, v_i)) = c((v_{i+3}, v_i))\) and \(c((v_{i+4}, v_{i+3})) = c((v_i, v_{i+3}))\). Now, color two i-vertices \((v_{i+1}, v_i)\) and \((v_{i+2}, v_{i+3})\) with colors 3 and 2, respectively. It can be easily seen that there are at least two available colors for each of i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+2})\). First, assign different colors to these two i-vertices. Also, color \((v_{i+2}, v_{i+1})\) and \((v_{i+1}, v_{i+2})\) as same as i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+2})\), respectively. By coloring two t-vertices \(v_{i+1}\) and \(v_{i+2}\) with different available colors, we have a proper \(v_i\)-simultaneous (6, 1)-coloring for G.

Now, suppose that \(f = [v_i v_{i+1} v_{i+2} \dots v_j], j \ge i+4\) and consider the graph \(G' = (G-v_{i+1})+e\) of order n-1 where \(e = \{v_i, v_{i+2}\}\). Then by induction, we conclude that G' has a vi-simultaneous (6,1)-coloring such as c. Color two i-vertices \((v_i, v_{i+1})\) and \((v_{i+1}, v_i)\) with colors \(c((v_i, v_{i+2}))\) and \(c((v_{i+2}, v_i))\), respectively. Also, assign color \(c((v_i, v_{i+2}))\) to the i-vertex \((v_{i+2}, v_{i+1})\). Now, we are going to recolor vertices \((v_{i+3}, v_{i+2})\) and \(v_{i+2}\) and color \(v_{i+1}\) and i-vertex \((v_{i+1}, v_{i+2})\) as well. It can be easily seen that, there is at least one available color for both i-vertices \((v_{i+3}, v_{i+2})\) and \((v_{i+1}, v_{i+2})\). After coloring these i-vertices, there are at least 2 available colors for the vertices \(v_{i+1}\) and \(v_{i+2}\). By coloring these vertices with different colors, we have a proper \(v_i\)-simultaneous (6,1)-coloring of G.

Theorem 3.6. If G is a 2-connected outerplanar graph with \(\Delta(G) \geq 4\) and \(g(G) \geq 4\), then \(\chi_{vi,1}(G) \leq \Delta(G) + 3\).

Proof. We prove the theorem by induction on the number of vertices of G. Since G is 2-connected, \(\Delta \geq 4\) and \(g \geq 4\), G has at least eight vertices. In Figure 7, a vi-simultanious (6,1)-coloring of the only 2-connected outerplanar graph of order 8 with maximum degree 4 and girth at least 4 is shown.

Let G be a 2-connected outerplanar graph of order n and \(\Delta(G) = \Delta\). Since \(\Delta \geq 4\) and \(g(G) \geq 4\), G has an end face \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) of degree at least 4.

Suppose that the theorem is true for all 2-connected outerplanar graphs with maximum degree at least 4, girth at least 4 and less than n vertices. Consider the end face \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\)

Figure 7: A 2-connected outerplanar graph of order 8 with maximum degree 4 and girth 4.

of degree at least 4 and let H be the induced subgraph of G on t-vertices of f with degree 2. If \(\Delta(G \setminus H) \leq 3\), then by Theorem 3.5, \((G \setminus H)^{\frac{3}{3}}\) has a 6-proper coloring, named c in which for any vertex \(u \in V(G \setminus H)\), \(|\{c(v) : v \in I_2(u)\}| = 1\). Also, if \(\Delta(G \setminus H) \geq 4\), then by induction hypothesis, c is a \((\Delta + 3)\)-proper coloring for \((G \setminus H)^{\frac{3}{3}}\) with desired property. It is enough to extend c to a \((\Delta + 3)\)-proper coloring of \(G^{\frac{3}{3}}\) with desired property of the theorem.

First suppose that \(f = [v_i v_{i+1} v_{i+2} v_{i+3}]\). Consider the graph \(G \setminus H\) and its desired coloring c with at most \((\Delta + 3)\) colors. First, color two i-vertices \((v_{i+1}, v_i)\) and \((v_{i+2}, v_{i+3})\) as same as i-vertices \((v_{i+3}, v_i)\) and \((v_i, v_{i+3})\), respectively. Now color two i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+2})\) with different available colors. Also, color two i-vertices \((v_{i+2}, v_{i+1})\) and \((v_{i+1}, v_{i+2})\) as same as i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+3})\), respectively. Now it can be easily seen that each of t-vertices \(v_{i+1}\) and \(v_{i+2}\) have at least \(\Delta - 1 \geq 3\) available colors. By coloring those t-vertices we have a \((\Delta + 3)\)-coloring for \(G^{\frac{3}{3}}\) with the desired property.

Now, suppose that \(f=[v_iv_{i+1}\dots v_{j-1}v_j]\) is an end face of degree at least 5 with \(j\geq i+4\) and consider the graph \(G'=(G-v_{i+1})+e\) of order n-1 where \(e=\{v_i,v_{i+2}\}\). Then by induction, we conclude that G' has a vi-simultaneous \((\Delta+3,1)\)-coloring such as c. Color two i-vertices \((v_i,v_{i+1})\) and \((v_{i+1},v_i)\) with colors \(c((v_i,v_{i+2}))\) and \(c((v_{i+2},v_i))\), respectively. Also, assign color \(c((v_i,v_{i+2}))\) to the i-vertex \((v_{i+2},v_{i+1})\). Now, we are going to recolor the vertices \((v_{i+3},v_{i+2})\) and \(v_{i+2}\) and color the vertices \(v_{i+1}\) and \(v_{i+1}\) and \(v_{i+2}\) as well. It can be easily seen that, there are two

available colors for both i-vertices \((v_{i+3}, v_{i+2})\) and \((v_{i+1}, v_{i+2})\). After coloring these i-vertices with the same color, there are at least \(3 \le \Delta - 1\) available colors for each of the t-vertices \(v_{i+1}\) and \(v_{i+2}\). By coloring these vertices with different colors, we have a \((\Delta + 3, 1)\)-coloring for \(G^{\frac{3}{3}}\) with desired property of the theorem.

According to Theorems 2.2, 2.3, 2.8, 3.5, and 3.6, we conclude the following result. A cycle \(C_3\) is often called a triangle and a triangle-free graph is a graph containing no triangle.

Theorem 3.7. \(\chi_{vi,1}(G) \leq \Delta(G) + 3\) for any triangle-free outerplanar graph.

Theorem 3.8. If G is a 2-connected outerplanar graph with \(\Delta(G) = \Delta \geq 4\) and \(g(G) = g \geq 6\), then \(\chi_{vi,1}(G) = \Delta(G) + 2\).

Proof. We prove the theorem by induction on the number of vertices of G. Since G is 2-connected, \(\Delta \geq 4\) and \(g \geq 6\), G has at least 14 vertices. In Figure 8, a vi-simultanious (6,1)-coloring of the only 2-connected outerplanar graph of order 14 with maximum degree 4 and girth at least 6 is shown.

Let |V(G)|=n and suppose that the theorem is true for all 2-connected outerplanar graphs with maximum degree at least 4, girth at least 6 and less than n vertices. Since \(\chi_{vi}(G) \geq \Delta + 2\), it suffices to present a \((\Delta + 2)\)-proper coloring for \(G^{\frac{3}{3}}\). Since \(\Delta \geq 4\) and \(g(G) \geq 6\), G has an end face \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) of degree at least 6.

Figure 8: A 2-connected outerplanar graph of order 14 with maximum degree 4 and girth 6.

Consider the end face \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) of degree at least 6 and let H be the induced subgraph of G on t-vertices of f with degree 2. If \(\Delta(G \setminus H) \leq 3\), then by Theorem 3.5, \((G \setminus H)^{\frac{3}{3}}\) has a 6-proper coloring, named c in which for any vertex \(u \in V(G \setminus H)\), \(|c(I_2(u))| = 1\). Also, if \(\Delta(G \setminus H) \geq 4\), then by induction hypothesis, c is a \((\Delta + 2)\)-proper coloring for \((G \setminus H)^{\frac{3}{3}}\) with desired property. It is enough to extend c to a \((\Delta + 2)\)-proper coloring of \(G^{\frac{3}{3}}\) with desired property of the theorem.

First suppose that \(f = [v_i v_{i+1} v_{i+2} v_{i+3} v_{i+4} v_{i+5}]\). Consider the graph \(G \setminus H\) with its \((\Delta + 2)\)-desired coloring c. First, color two i-vertices \((v_{i+1}, v_i)\) and \((v_{i+4}, v_{i+5})\) as same as i-vertices

\((v_{i+5},v_i)\) and \((v_i,v_{i+5})\), respectively. Now color each of the i-vertices \((v_i,v_{i+1})\) and \((v_{i+5},v_{i+4})\) with at least one available color. Also, color two i-vertices \((v_{i+2},v_{i+1})\) and \((v_{i+3},v_{i+4})\) as same as the i-vertices \((v_i,v_{i+1})\) and \((v_{i+5},v_{i+4})\), respectively. Now, each of the i-vertices \((v_{i+1},v_{i+2})\) and \((v_{i+4},v_{i+3})\) has at least \(3 \leq \Delta - 1\) available colors. Color them with different colors. Also, color \((v_{i+2},v_{i+3})\) and \((v_{i+3},v_{i+2})\) as same as the i-vertices \((v_{i+4},v_{i+3})\) and \((v_{i+1},v_{i+2})\), respectively. Now it can be easily seen that each of the t-vertices \(v_{i+1}\) and \(v_{i+4}\) has at least \(2 \leq \Delta - 2\) available colors and t-vertices \(v_{i+2}\) and \(v_{i+3}\) have at least \(3 \leq \Delta - 1\) available colors. By coloring these t-vertices, we have a \((\Delta + 2)\)-coloring for \(G^{\frac{3}{3}}\) with the desired property.

Now, suppose that \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) is an end face of degree at least 5 with \(j \geq i+4\) and consider the graph \(G' = (G-v_{i+1})+e\) of order n-1 where \(e = \{v_i, v_{i+2}\}\). Then by induction, we conclude that G' has a \(v_i\)-simultaneous \((\Delta+3,1)\)-coloring such as c. Color two i-vertices \((v_i, v_{i+1})\) and \((v_{i+1}, v_i)\) with colors \(c((v_i, v_{i+2}))\) and \(c((v_{i+2}, v_i))\), respectively. Also, assign color \(c((v_i, v_{i+2}))\) to the i-vertex \((v_{i+2}, v_{i+1})\). Now, we are going to recolor the vertices \((v_{i+3}, v_{i+2})\) and \(v_{i+2}\) and color the vertices \(v_{i+1}\) and \(v_{i+1}\) and \(v_{i+2}\) as well. It can be easily seen that, there are two available colors for both i-vertices \(v_{i+1}\) and \(v_{i+2}\) and \(v_{i+1}\) and \(v_{i+2}\). After coloring these i-vertices with the same color, there are at least \(0 \leq \Delta-1\) available colors for each of the v-vertices \(v_{i+1}\) and \(v_{i+2}\). By coloring these vertices with different colors, we have a v-vertices for v-vertices v-vertices with desired property of the theorem.

Now, suppose that \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) is an end face of degree at least 7 with \(j \geq i+6\) and consider the graph \(G' = (G - v_{i+1}) + e\) of order n-1 where \(e = \{v_i v_{i+2}\}\). Then by induction, we conclude that G' has a \(v_i\)-simultaneous \((\Delta + 2, 1)\)-coloring such as c. Color two i-vertices \((v_i, v_{i+1})\) and \((v_{i+1}, v_i)\) with colors \(c((v_i, v_{i+2}))\) and \(c((v_{i+2}, v_i))\), respectively. Also, assign color \(c((v_i, v_{i+2}))\) to the i-vertex \((v_{i+2}, v_{i+1})\). Now, we are going to recolor vertices \((v_{i+3}, v_{i+2})\) and \(v_{i+2}\) and color the vertices \(v_{i+1}\) and \(v_{i+1}\) and \(v_{i+2}\) as well. It can be easily seen that, there is one available color for both i-vertices \(v_{i+3}, v_{i+2}\) and \(v_{i+2}\) and \(v_{i+2}\). After coloring these i-vertices with the same color, there are \(v_{i+3}\) are \(v_{i+3}\) and \(v_{i+2}\) and \(v_{i+2}\). By coloring these vertices with different colors, we have a \(v_i\)-simultaneous \(v_i\)-simultaneous \(v_i\)-simultaneous \(v_i\)-simultaneous \(v_i\)-simultaneous \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring these vertices with different colors, we have a \(v_i\)-simultaneous \(v_i\)-simultaneous \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring these vertices with different colors, we have a \(v_i\)-simultaneous \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring these vertices \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)

Theorem 3.9. [16] If G is a 2-connected outerplanar graph, then G has an end face \(f = [v_i v_{i+1} \dots v_j]\), where either \(deg(v_i) < 5\) or \(deg(v_j) < 5\).

Theorem 3.10. If G is a 2-connected outerplanar graph of order n with \(\Delta(G) = \Delta \geq 5\) and \(g(G) = g \geq 4\), then \(\chi_{vi,1}(G) = \Delta(G) + 2\).

Proof. We prove the theorem by induction on the order of G. Since G is 2-connected, \(\Delta \geq 5\) and \(g \geq 4\), G has at least 10 vertices. In Figure 9, a vi-simultanious (7,1)-coloring of the only 2-connected outerplanar graph of order 10 with maximum degree 5 and girth at least 4 is shown.

Suppose that the theorem is true for all 2-connected outerplanar graphs with maximum degree at least 5, girth at least 4 and less than n vertices. By Theorem 3.9, there is an end face \(f = [v_i v_{i+1} \dots v_j]\) of G of degree at least 4, where either \(deg(v_i) < 5\) or \(deg(v_j) < 5\). Let H be the induced subgraph of G on t-vertices of f with degree 2.

If \(\Delta(G \setminus H) = 4\), then by Theorem 3.6, \((G \setminus H)^{\frac{3}{3}}\) has a 7-proper coloring, named c in which for any vertex \(u \in V(G \setminus H)\), \(|c(I_2(u))| = 1\). Also, if \(\Delta \geq 5\), then by induction hypothesis, c

Figure 9: A 2-connected outerplanar graph of order 10 with maximum degree 5 and girth 4.

is a \((\Delta+2)\)-proper coloring for \((G\setminus H)^{\frac{3}{3}}\) with desired property. It is enough to extend c to a \((\Delta+2)\)-proper coloring of \(G^{\frac{3}{3}}\) with the desired property of the theorem.

First suppose that \(f = [v_i v_{i+1} v_{i+2} v_{i+3}]\). Consider the graph \(G \setminus H\) and its desired coloring c with at most \((\Delta + 2)\) colors. First, color two i-vertices \((v_{i+1}, v_i)\) and \((v_{i+2}, v_{i+3})\) as same as the i-vertices \((v_{i+3}, v_i)\) and \((v_i, v_{i+3})\), respectively. Now color two i-vertices \((v_i, v_{i+1})\) and \((v_{i+3}, v_{i+2})\) with different available colors. Note that, since at least one of the t-vertices \(v_i\) or \(v_{i+3}\) is of degree at most \(v_i\) in \(v_i\), there are different available colors for these two \(v_i\)-vertices. Also, color two \(v_i\)-vertices \(v_i\) and \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-vertices \(v_i\)-ve

Now it can be easily seen that, each of t-vertices \(v_{i+1}\) and \(v_{i+2}\) has at least \(3 \le \Delta - 2\) available colors. By coloring these t-vertices we have a \((\Delta + 2)\)-coloring for \(G^{\frac{3}{3}}\) with the desired property.

Now, suppose that \(f = [v_i v_{i+1} \dots v_{j-1} v_j]\) is an end face of degree at least 5 with \(j \geq i+4\) and consider the graph \(G' = (G-v_{i+1})+e\) of order n-1 where \(e = \{v_i v_{i+2}\}\). Then by induction, we conclude that G' has a \(v^i\)-simultaneous \((\Delta+2,1)\)-coloring such as c. Color two i-vertices \((v_i,v_{i+1})\) and \((v_{i+1},v_i)\) with colors \(c((v_i,v_{i+2}))\) and \(c((v_{i+2},v_i))\), respectively. Also, assign color \(c((v_i,v_{i+2}))\) to the i-vertex \((v_{i+2},v_{i+1})\). Now, we are going to recolor vertices \((v_{i+3},v_{i+2})\) and \(v_{i+2}\) and color the vertices \(v_{i+1}\) and \(v_{i+1}\) and \(v_{i+2}\) as well. It can be easily seen that, there is one available color for both i-vertices \(v_{i+3},v_{i+2}\) and \(v_{i+2}\) and \(v_{i+2}\). After coloring these i-vertices with the same color, there are \(v_{i+3}\) and \(v_{i+2}\) are \(v_{i+3}\) and \(v_{i+2}\). By coloring these vertices with different colors, we have a \(v_i\)-simultaneous \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring for \(v_i\)-coloring the proof.

According to Theorems 3.8 and 3.10, any outerplanar graph G is of vi-class 1 when G is (1) triangle-free and \(\Delta(G) \geq 5\) or (2) \(\Delta(G) = 4\) and \(g(G) \geq 6\).

Problem 1. Charactrize all outerplanar graphs of vi-class one.

Acknowledgement

We would like to thank the referee for the careful reading of the paper and for the suggestions which helped us to improve considerably the paper. This research was in part supported by a grant from IPM (No.1400050116).

References

• [1] I. Algor and N. Alon, The Star Arboricity of Graphs, Discrete Mathematics 43 (1989), 11–22.
• [2] M. Behzad, Graphs and their Chromatic Numbers, Ph.D. thesis, Michigan State University, 1965.
• [3] J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics 244, Springer, New York, 2008.
• [4] O.V. Borodin, Structural theorem on plane graphs with application to the entire coloring number, J. Graph Theory 23 (1996), 233–239.
• [5] O.V. Borodin, Simultaneous coloring of edges and faces of plane graphs, Discrete Math. 128 (1994), 21–33.
• [6] O.V. Borodin, Solution of Ringel's problems of the face and vertex coloring of plane graphs and coloring of 1-planar graphs, Metody Diskret. Analiza 41 (1984), 12–26 (in Russian).
• [7] R.A. Brualdi and J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993), 51–58.
• [8] M. Chen, J. Yang, H. Zhang, and Y. Wang, Weakly entire coloring of outerplanar graphs, Oper. Res. Trans. 25 (2021), 132–136.
• [9] J. Fiamcik, Simultaneous colouring of 4-valent maps, Mat. Casopis Sloven. Akad. Vied 21 (1971), 9–13.
• [10] M. Fiedler, Recent advances in graph theory, Proceedings of the Second Czechoslovak Symposium held in Prague, Prague, 544 pages, 1975.
• [11] E. Jucovic, On a problem in map colouring, Mat. Casopis Sloven. Akad. Vied 19 (1969), 225–227, errata, ibid. 20 (1970), 224.
• [12] H.V. Kronk and J. Mitchem, A seven-color theorem on the sphere, Discrete Math. 5 (1973), 253–260.
• [13] M.N. Iradmusa, On colorings of graph fractional powers, Discrete Math. 310 (2010), 1551– 1556.
• [14] M. Mozafari-Nia and M.N. Iradmusa, A note on coloring of ³ 3 -power of subquartic graphs, Australasian J. of Combinatorics 79 (2021), 454–460.

• [15] M. Mozafari-Nia and M.N. Iradmusa, Simultaneous coloring of vertices and incidences of graphs, submitted (2021), https://arxiv.org/abs/2205.07189.
• [16] M. Mozafari-Nia and B. Omoomi, Injective chromatic number of outerplanar graphs, Taiwanese Journal of Mathematics 22 (2018), 1309–1320.
• [17] G. Ringel, Das Geschlecht des vollstandigen paaren Graphen, (German) ¨ Abh. Math. Sem. Univ. Hamburg 28 (1965), 139–150.
• [18] D.P. Sanders and Y. Zhao, On the entire colouring conjecture, Canad. Math. Bull. 43 (2000), 108–114.
• [19] A. O. Waller, Simultaneously colouring the edges and faces of plane graphs, J. Combin. Theory Ser. B 69 (1997), 219–221.
• [20] F. Wang and X. Liu, Coloring 3-power of 3-subdivision of subcubic graph, Discrete Mathematics, Algorithms and Applications 10 (3), 1850041 (2018).
• [21] W. Wang and J. Liu, On the vertex face total chromatic number of planar graphs, J. Graph Theory 22 (1996), 29–37.
• [22] W. Wang and X. Zhu, Entire colouring of plane graphs, Journal of Combinatorial Theory, Series B 101 (2011), 490–501.
• [23] D.B. West, Introduction to Graph Theory, Prentice Hall, Second edition, 2001.