# On the rainbow planar Turán number of paths

Ervin Győri  Alfréd Rényi Institute of Mathematics, Budapest  Ryan R. Martin
Iowa State University, Ames  Addisu Paulos  Eötvös Loránd University, Budapest
Addis Ababa University, Addis Ababa  Casey Tompkins  Alfréd Rényi Institute of
Mathematics, Budapest  Kitti Varga  Budapest University of Technology and
Economics, Budapest  MTA-ELTE Egerváry Research Group, Budapest

###### Abstract

An edge-colored graph is said to contain a rainbow-$F$ if it contains $F$ as a
subgraph and every edge of $F$ is a distinct color. The problem of maximizing
edges among $n$-vertex properly edge-colored graphs not containing a
rainbow-$F$, known as the rainbow Turán problem, was initiated by Keevash,
Mubayi, Sudakov and Verstraëte. We investigate a variation of this problem
with the additional restriction that the graph is planar, and we denote the
corresponding extremal number by $\operatorname{ex}_{\mathcal{P}}^{*}(n,F)$.
In particular, we determine $\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{5})$,
where $P_{5}$ denotes the $5$-vertex path.

##  1 Introduction

An edge-coloring of a graph $F$ is a _proper edge-coloring_ if no two incident
edges of $F$ receive the same color. An edge-colored graph $F$ is called
_rainbow_ if no two edges of $F$ receive the same color, and in short we call
it a _rainbow- $F$_. A properly edge-colored graph $G$ is called _rainbow-
$F$-free_ if it contains no rainbow-$F$ as a subgraph with the underlying
edge-coloring of $G$.

######  Definition 1.

Let $n$ be a positive integer and $F$ be a fixed graph. The rainbow Turán
number of $F$, denoted as $\operatorname{ex}^{*}(n,F)$, is the maximum number
of edges in a properly edge-colored $n$-vertex rainbow-$F$-free graph.

Clearly $\operatorname{ex}(n,F)\leq\operatorname{ex}^{*}(n,F)$. Indeed, any
properly edge-colored $F$-free graph is rainbow-$F$-free. In fact, Keevash,
Mubayi, Sudakov, and Verstraëte [8] proved the following.

######  Theorem 1 (Keevash et al. [8]).

For any graph $F$ and positive integer $n$,

$\operatorname{ex}(n,F)\leq\operatorname{ex}^{*}(n,F)\leq\operatorname{ex}(n,F)+o(n^{2}).$

Let $P_{k}$ denote a path on $k$ vertices. Recently Johnston, Palmer and
Sarkar [6] initiated the study of rainbow Turán number of paths. They obtained
sharp upper bounds for the rainbow Turán number of $P_{4}$ and $P_{5}$.

######  Theorem 2 (Johnston, Palmer and Sarkar [6]).

  1. 1.

If $n$ is divisible by $4$, then $\operatorname{ex}^{*}(n,P_{4})={3n}/{2}.$

  2. 2.

If $n$ is divisible by $8$, then $\operatorname{ex}^{*}(n,P_{5})=2n.$

In the same paper they obtained a general upper bound which works for all
$P_{k}$. Moreover they obtained constructions giving lower bound and posed
their conjecture.

######  Theorem 3 (Johnston, Palmer and Sarkar [6]).

For any positive integers $n$ and $k$,

$\left(\frac{k-1}{2}\right)n+O(1)\leq\operatorname{ex}^{*}(n,P_{k})\leq\left\lceil{\frac{3k-2}{2}}\right\rceil
n.$

######  Conjecture 1 (Johnston, Palmer and Sarkar [6]).

For $k\geq 6$,

$\operatorname{ex}^{*}(n,P_{k})=\left(\frac{k-1}{2}\right)n+O(1).$

Recently Ergemlidze, Győri and Methuku [1] improved the upper bound.

######  Theorem 4 (Ergemlidze, Győri and Methuku [1]).

For any positive integers $n$ and $k$,

$\operatorname{ex}^{*}(n,P_{k})\leq\left(\frac{9k+5}{7}\right)n.$

Continuing the study, Halfpap [3] obtained a sharp upper bound for the rainbow
Turán number of $P_{6}$ and the result partially confirms the conjecture of
Johnston, Palmer and Sarkar.

######  Theorem 5 (Halfpap [3]).

For any positive integer $n$, $\operatorname{ex}^{*}(n,P_{6})\leq{5n}/{2}.$

The articles [2, 4, 5, 7] contain further results on rainbow-type extremal
graph problems. In this paper, we consider rainbow Turán numbers in the family
of planar graphs. The following notations are important in the upcoming
sections.

Let $G$ be a graph. We denote the vertex and the edge sets of $G$ by $V(G)$
and $E(G)$, respectively. The number of vertices and the number of edges of
$G$ are denoted by $v(G)$ and $e(G)$, respectively. For a vertex $v\in V(G)$,
$d_{G}(v)$ denotes the degree of $v$. We may omit the subscript whenever there
is no ambiguity about the underlying graph.

For two vertices $u,v\in V(G)$, $\mathrm{dist}_{G}(u,v)$ denotes the distance
between $u$ and $v$. Let $N_{1}(v)$ and $N_{2}(v)$ denote the set of neighbors
and that of the second neighbors of $v$, respectively. i.e., $N_{1}(v)=\\{u\
|\ u\in V(G)\ \text{and}\ \mathrm{dist}_{G}(u,v)=1\\}$ and $N_{2}(v)=\\{u\ |\
u\in V(G)\ \text{and}\ \mathrm{dist}_{G}(u,v)=2\\}$. Denote
$N[v]=N(v)\cup\\{v\\}$. For simplicity, we may use the notation $N(v)$ instead
of $N_{1}(v)$.

The path and the cycle on $k$ vertices are denoted by $P_{k}$ and $C_{k}$,
respectively. A cycle on $k$ vertices is also referred as a $k$-cycle. For any
$S\subseteq V(G)$, $G[S]$ denotes the subgraph of $G$ induced by $S$.

For graphs $G$ and $H$, we denote by $G\cup H$ the disjoint union of $G$ and
$H$, and we denote by $G+H$ the join of $G$ and $H$, i.e. the graph obtained
by connecting each pair of vertices between a vertex-disjoint copy of $G$ and
$H$.

##  2 Rainbow planar Turán number of paths

######  Definition 2.

Let $n$ be a positive integer and $F$ be a fixed graph. The rainbow planar
Turán number of $F$, denoted by $\operatorname{ex}_{\mathcal{P}}^{*}(n,F)$, is
the maximum number of edges in an $n$-vertex rainbow-$F$-free edge-colored
planar graph.

A properly edge-colored planar graph is rainbow-$P_{3}$-free if and only if
the graph is a matching plus isolated vertices. Thus,
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{3})=\left\lfloor{{n}/{2}}\right\rfloor$.

An extremal construction showing the first bound in Theorem 2 is sharp can be
obtained by taking disjoint copies of $K_{4}$ with a proper $3$-edge coloring
as pictured in Figure 1. Clearly, the graph is planar, and hence we have
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{4})\leq{3n}/{2}$.

123321123321123321 Figure 1: A $3$-edge colored graph which is
rainbow-$P_{4}$-free.

As mentioned earlier, this paper is mainly focused on determining the rainbow
planar Turán number of $P_{5}$, i.e.,
$\operatorname{ex}^{*}_{\mathcal{P}}(n,P_{5})$. Interestingly, the values are
the same as the sharp upper bound of the rainbow planar Turán number of
$P_{4}$ which is stated in Theorem 2.

For longer paths, the following theorem verifies that when $k\geq 8$ we have
maximal planar graphs avoiding rainbow paths of length $k$. However, the case
of $P_{6}$ and $P_{7}$ still seems quite interesting. In section 9, we pose
our conjectures concerning the rainbow planar Turán number of these paths.

######  Theorem 6.

For $n\geq k\geq 8$,

$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{k})=3n-6.$

###### Proof.

First, let $n$ be even. Take a double-wheel, $W_{n}=(K_{1}\cup
K_{1})+C_{n-2}$. Note that $W_{n}$ has two vertices of degree $n-2$ and all
the remaining vertices are of degree $4$. Let the $(n-2)$-cycle be
$v_{1}v_{2}v_{3}\dots v_{n-1}v_{n-2}v_{1}$ and the two high-degree vertices be
$u$ and $w$.

We define an edge-coloring $c$ of $W_{n}$, which uses $2n-2$ distinct colors,
as follows. Let $c(uv_{i})=a_{i}$ and $c(wv_{i})=b_{i}$ for any
$i\in\\{1,2,\dots,n-2\\}$, and alternately color the edges of the
$(n-2)$-cycle using two other colors $a$ and $b$.

Now we show that with this edge-coloring, $W_{n}$ is rainbow-$P_{k}$-free for
any $k\geq 8$. Consider a path of length $7$ in $W_{n}$. This path contains at
most $4$ edges which are not in the $(n-2)$-cycle. Thus, the number of edges
which are on this cycle is at least $3$ and hence the path is not rainbow.
Since $W_{n}$ is a maximal planar graph, we have
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{k})=3n-6$.

Now let $n$ be odd. In this case, take a maximal planar graph
$H_{n}=K_{2}+P_{n-2}$. Let the path $P_{n-2}$ be $v_{1}v_{2}v_{3}\dots
v_{n-1}v_{n-2}$ and let the remaining two vertices be $u$ and $w$. Define an
edge-coloring $c$ of $H_{n}$, which uses $2n-3$ distinct colors, as follows.
Let $c(uv_{i})=a_{i}$ for any $i\in\\{2,3,\dots,n-3\\}$, let $c(wv_{i})=b_{i}$
for any $i\in\\{1,2,3\dots,n-2\\}$, let $c(uw)=d$, and alternately color the
edges of the even cycle $uv_{1}v_{2}v_{3}\dots v_{n-2}u$ using two other
colors $a$ and $b$.

Again, it is not difficult to see that $c$ is a proper edge-coloring and any
path of length $7$ contains at least three edges of the $(n-1)$-cycle
$uv_{1}v_{2}\dots v_{n-2}u$. Thus, every $P_{8}$ of $H_{n}$ is not rainbow.
Since $H_{n}$ is a maximal planar graph, we have
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{k})=3n-6$. ∎

##  3 Main results and extremal constructions

The following theorem is our main result and it gives the exact value of the
rainbow planar Turán number of $P_{5}$.

######  Theorem 7.

For $n\geq 4$,
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{5})=\left\lfloor{{3n}/{2}}\right\rfloor.$

The extremal constructions pictured in Figure 1 contain no rainbow-$P_{5}$,
and thereby verify that the bound
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{5})\leq\left\lfloor{{3n}/{2}}\right\rfloor$
is sharp. Next we give a properly edge-colored rainbow-$P_{5}$-free planar
graph $G_{n}$ on $n\geq 5$ vertices with
$e(G_{n})=\left\lfloor{{3n}/{2}}\right\rfloor.$

### Constructions of $G_{5}$ and $G_{7}$.

A $5$-vertex and $7$-edge planar graph $G_{5}$ with a proper edge-coloring is
shown in Figure 2 (left). Moreover, a $7$-vertex and $10$-edge planar graph
$G_{7}$ with a proper edge-coloring is shown in Figure 2 (right). Observe that
both $G_{5}$ and $G_{7}$ are rainbow-$P_{5}$-free graphs and
$e(G_{5})=\left\lfloor{{3n}/{2}}\right\rfloor=7$ and
$e(G_{7})=\left\lfloor{{3n}/{2}}\right\rfloor=10$.

12344321234342143 Figure 2: The graphs $G_{5}$ and $G_{7}$.

### Constructions of $G_{n}$ when $n$ is even and $n\geq 4$.

For $n=4$, we may take $G_{n}$ to be $K_{4}$. Its proper $3$-edge coloring is
already given in Figure 1. Figure 3 shows the constructions of $G_{n}$ with a
proper $3$-edge coloring when $n\geq 6$ is even. Clearly, $G_{n}$ is
rainbow-$P_{5}$-free. Moreover, $G_{n}$ is $3$-regular and
$e(G_{n})=\left\lfloor{{3n}/{2}}\right\rfloor$.

### Constructions of $G_{n}$ when $n$ is odd and $n\geq 9$.

For any odd number $n\geq 9$, we may take $G_{n}$ to be the disjoint union of
$G_{n-5}$ and $G_{5}$, i.e., $G_{n}=G_{n-5}\cup G_{5}$. Then
$e(G_{n})=\left\lfloor{{3(n-5)/}{2}}\right\rfloor+7=\left\lfloor{{3n}/{2}}\right\rfloor$.
By induction, $G_{n}$ is rainbow-$P_{5}$-free.

$a_{1}$$a_{n/2}$$b_{1}$$b_{n/2}$1212112121223333333$a_{1}$$a_{n/2}$$b_{1}$$b_{n/2}$1212121212123323333331
Figure 3: A $3$-edge coloring of $G_{n}$ when $n/2$ is even (left) and when
$n/2$ is odd (right) for even integers $n\geq 6$.

##  4 Outline of the proof of Theorem 7

From the extremal constructions discussed in the previous section, we have
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{5})\geq\left\lfloor{{3n}/{2}}\right\rfloor$.
In the upcoming sections, we prove
$\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{5})\leq\left\lfloor{{3n}/{2}}\right\rfloor$,
thereby completing the proof of Theorem 7. The proof includes an induction
argument and discharging methods. To manage the flow of the proof, we break it
into four sections.

In Section 5, some basic preliminaries for the proof are given. The section
examines some important graph structures together with proper edge-coloring
schemes under the assumption that the graph avoids a rainbow-$P_{5}$.

In Section 6, we analyze thoroughly the situations for which we can finish the
proof by induction. In this section, we also show why the planar Turán number
and the rainbow planar Turán number of $P_{5}$ behave quite differently.

Section 7 gives more refinements on the graph by avoiding vertices of degree
at least five and two degree-$4$ vertices sharing a common vertex. Moreover,
in this section we show each degree-$4$ vertex has at least two degree-$2$
vertices in its neighbor or second neighbor.

We finish the proof in Section 8. In this section we define a modification
$\tilde{d}$ of the degree function, for which $\tilde{d}(v)\leq 3$ holds for
each vertex $v$ of the graph. This lets us to conclude the proof using the
handshaking lemma.

##  5 Preliminaries

We need the following basic preliminary proper edge-coloring schemes which
avoid a rainbow-$P_{5}$. The results are important in the upcoming sections of
the proof.

######  Definition 3.

The _bow tie graph_ is two $3$-cycles sharing exactly one vertex (see Figure 4
(left)). We refer to a bow tie with its vertices labelled as in the figure as
a $(u_{1}u_{2}u,uu_{3}u_{4})$-bow tie.

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u$$w$ Figure 4:
The bow tie graph and the fish graph.

######  Lemma 1 (The bow tie coloring schemes).

Consider a $(u_{1}u_{2}u,uu_{3}u_{4})$-bow tie with a proper edge-coloring $c$
which avoids a rainbow-$P_{5}$. Without loss of generality, we can assume
$c(uu_{i})=i$ for any $i\in\\{1,2,3,4\\}$. Then $c(u_{1}u_{2})=c(u_{3}u_{4})$
and this color is not in $\\{1,2,3,4\\}$.

###### Proof.

Consider the $5$-vertex path $u_{1}u_{2}uu_{3}u_{4}$. Since $c$ is a
rainbow-$P_{5}$-free edge-coloring, it can be seen that either
$c(u_{1}u_{2})=c(u_{3}u_{4})$ and this color is not in $\\{1,2,3,4\\}$, or
$c(u_{1}u_{2})=3$, or $c(u_{3}u_{4})=2$.

Suppose the first case does not hold. Without loss of generality, we can
assume $c(u_{1}u_{2})=3$. Considering the paths $u_{3}u_{4}uu_{1}u_{2}$ and
$u_{3}u_{4}uu_{2}u_{1}$, we obtain that $c(u_{3}u_{4})$ is respectively in
$\\{1,3\\}$ and $\\{2,3\\}$. This implies, $c(u_{3}u_{4})=3$. This is a
contradiction as $uu_{3}$ is an edge incident to $u_{3}u_{4}$ and yet colored
with $3$. This completes the proof of Lemma 1. ∎

######  Definition 4.

The _fish graph_ is a $3$-cycle and a $4$-cycle sharing exactly one vertex
(see Figure 4 (right)). We refer to the fish graph with vertices labelled as
in the figure as a $(u_{1}u_{2}u,uu_{3}wu_{4})$-fish.

######  Lemma 2 (The fish graph coloring schemes).

Given a $(u_{1}u_{2}u,uu_{3}wu_{4})$-fish with a proper edge-coloring $c$
which avoids a rainbow-$P_{5}$, we have $c(wu_{3})=c(uu_{4})$ and
$c(wu_{4})=c(uu_{3})$, moreover either $c(u_{1}u_{2})=c(uu_{3})$ or
$c(u_{1}u_{2})=c(uu_{4})$.

###### Proof.

Without loss of generality, we can assume $c(uu_{i})=i$ for any
$i\in\\{1,2,3,4\\}$. Clearly, $c(u_{1}u_{2})$ is different from $1$ and $2$.
Suppose for contradiction $c(u_{1}u_{2})\notin\\{3,4\\}$. The we can assume
$c(u_{1}u_{2})=5$. Considering the paths $wu_{3}uu_{2}u_{1}$ and
$wu_{3}uu_{1}u_{2}$, we obtain that $c(u_{3}w)$ is respectively in $\\{2,5\\}$
and $\\{1,5\\}$, which implies $c(u_{3}w)=5$. Consequently, considering the
path $u_{3}wu_{4}uu_{1}$, we get $c(wu_{4})=1$. But this results in a
contradiction as we get a rainbow-$P_{5}$ path $u_{3}wu_{4}uu_{2}$, whose
edges are of colors 5, 1, 4, and 2, in this order.

Therefore, by the symmetry of the fish graph, we can assume $c(u_{1}u_{2})=3$.
Considering the paths $wu_{4}uu_{1}u_{2}$ and $wu_{4}uu_{2}u_{1}$, we get
$c(wu_{4})$ is in $\\{1,3\\}$ and $\\{2,3\\}$, respectively. This implies,
$c(wu_{4})=3$. For a similar reason, we obtain $c(wu_{3})=4$. This completes
the proof of Lemma 2. ∎

######  Definition 5.

A _medium-pair_ is three distinct cherries with common end vertices, i.e.,
$K_{2,3}$, see Figure 5 (left). A _heavy-pair_ is four distinct cherries with
common end vertices, i.e., $K_{2,4}$, see Figure 5 (right).

$w$$v$$u_{1}$$u_{2}$$u_{3}$$w$$v$$u_{1}$$u_{2}$$u_{4}$$u_{3}$ Figure 5: A
medium-pair and a heavy-pair.

######  Lemma 3 (The medium-pair coloring schemes).

Given a medium-pair with cherries $vu_{i}w$, where $i\in\\{1,2,3\\}$, let $c$
be a proper edge-coloring of it which avoids a rainbow-$P_{5}$. Then $c$ uses
either

  1. 1.

four colors, where two of which are applied in edges of two of its cherries,
or

  2. 2.

three colors, where $c(vu_{i})\in\\{c(wu_{1}),\ c(wu_{2}),\ c(wu_{3})\\}$ for
any $i\in\\{1,2,3\\}$.

For instance in the first case, we may have the cherries $vu_{1}w$ and
$vu_{2}w$ to which $c$ assigns only two colors: $c(vu_{1})=c(wu_{2})$ and
$c(vu_{2})=c(wu_{1})$. On the other hand, in the second case, we may have the
edge-coloring $c(vu_{1})=c(wu_{3}),\ c(vu_{2})=c(wu_{1})$ and
$c(vu_{3})=c(wu_{2})$.

For the purpose of simplicity, we sometimes refer to the first case as a
_four-coloring scheme_ and the second case as a _three-coloring scheme_ for
the medium-pair. Next we give the proof of Lemma 3.

###### Proof of Lemma 3.

Without loss of generality, we can assume $c(vu_{i})=i$ for $i\in\\{1,2,3\\}$.
Since $c$ is a rainbow-$P_{5}$-free coloring, it is not difficult to check
that at most one edge in $\\{wu_{1},wu_{2},wu_{3}\\}$ receives a color
different from 1, 2, 3.

Suppose (2) does not occur. Then t most one edge in
$\\{wu_{1},wu_{2},wu_{3}\\}$ receives a color not in $\\{1,2,3\\}$. Without
loss of generality, we can assume $c(wu_{3})=4$. Considering the paths
$u_{3}wu_{2}vu_{1}$ and $u_{3}wu_{1}vu_{2}$, we get $c(wu_{2})=1$ and
$c(wu_{1})=2$. This completes the proof of Lemma 3. ∎

######  Lemma 4.

Let $G$ be a rainbow-$P_{5}$-free graph containing a medium pair and let
$vu_{i}w$ be the $3$ cherries forming this medium-pair where
$i\in\\{1,2,3\\}$. Then $v$ is adjacent to at most one vertex in
$V(G)\setminus\\{u_{1},u_{2},u_{3},w\\}$.

###### Proof.

Let $S=\\{u_{1},u_{2},u_{3},w\\}$. We distinguish two cases based on the
coloring scheme of the medium-pair as stated in Lemma 3.

Case 1: The medium-pair is colored with the three-coloring scheme.

Without loss of generality suppose, $c(vu_{1})=c(wu_{3})=1,\
c(vu_{2})=c(wu_{1})=2$ and $c(vu_{3})=c(wu_{2})=3$. In this case, we show that
there is no vertex $v^{*}\in V(G)\setminus S$ such that $vv^{*}\in E(G)$.
Indeed, suppose such a vertex exists in $G$. Clearly,
$c(vv^{*})\notin\\{1,2,3\\}$, so we can assume $c(vv^{*})=4$. However, this
results in a contradiction as the $v^{*}vu_{1}wu_{2}$ is a rainbow-$P_{5}$.

Case 2: The medium-pair is colored with the four-coloring scheme.

Without loss of generality, we can assume $c(vu_{1})=c(wu_{2})=1,\
c(vu_{2})=c(wu_{1})=2,\ c(vu_{3})=3$ and $c(wu_{3})=4$. Assume that there
exists a vertex $v^{*}\in V(G)\backslash S$ such that $vv^{*}\in E(G)$.
Considering the paths $v^{*}vu_{1}wu_{3}$ and $v^{*}vu_{2}wu_{3}$, we obtain
that $c(vv^{*})$ is in $\\{2,4\\}$ and $\\{1,4\\}$, respectively. Thus,
$c(u_{1}v)=4$. This implies that $v$ cannot be adjacent to more than a vertex
in $V(G)\backslash S$. This completes the proof of Lemma 4. ∎

######  Lemma 5 (The heavy-pair coloring schemes).

Consider a heavy-pair using the cherries $\ vu_{i}w$, where
$i\in\\{1,2,3,4\\}$, with a proper edge-coloring $c$ which avoids a
rainbow-$P_{5}$. Then $c$ uses only four colors and without loss of
generality, we can assume $c(wu_{2})=c(vu_{1})$, $c(wu_{1})=c(vu_{2})$,
$c(wu_{4})=c(vu_{3})$, and $c(wu_{3})=c(vu_{4})$.

###### Proof.

Without loss of generality, we can assume $c(vu_{i})=i$ for any
$i\in\\{1,2,3,4\\}$. It is easy to show for each $i\in\\{1,2,3,4\\}$, we have
$c(wu_{i})\in\\{1,2,3,4\\}$. Indeed, suppose not and without loss of
generality, assume $c(wu_{1})=5$. Then considering the path
$u_{1}wu_{2}vu_{3}$, we get $c(wu_{2})=3$. But this results in a contradiction
as we get rainbow-$P_{5}$ path $u_{1}wu_{2}vu_{4}$, whose edges are of colors
5, 3, 2, and 4, in this order.

Without loss of generality, we can assume $c(wu_{1})=c(vu_{2})=2$. Then
considering the paths $u_{2}wu_{1}vu_{3}$ and $u_{2}wu_{1}vu_{4}$, we get
$c(u_{2}w)=1$. Consequently, $c(u_{3}w)=4$ and $c(u_{4}w)=3$ hold, and this
completes the proof Lemma 5. ∎

##  6 Breaking the problem

From now on, by a graph $G$ we mean an $n$-vertex planar graph with a proper
edge-coloring $c$ which avoids a rainbow-$P_{5}$. The following are important
observations for the proof.

If $G$ contains two adjacent degree-2 vertices, then we can finish the proof
by induction after deleting these two vertices. Moreover, if $G$ contains a
vertex of degree at most 1, then again we can finish the proof by induction
after deleting this vertex. Even more, we can also finish the proof by
induction if we find a $k$-vertex component $H$ in $G$ such that
$e(H)\leq{3k}/{2}$. We call such a component a _nice-component_.

######  Definition 6.

Let $H$ be a subgraph of $G$. A vertex $v$ in $H$ is called _saturated_ if
$d_{H}(v)=d_{G}(v)$.

######  Lemma 6.

Let $(u_{1}u_{2}u,uu_{3}u_{4})$-bow tie be in $G$. Then $u_{1},u_{2},u_{3}$
and $u_{4}$ are saturated vertices. i.e., $d_{G}(u_{i})=2$,
$i\in\\{1,2,3,4\\}.$

###### Proof.

Denote $c(uu_{i})=i$, where $i\in\\{1,2,3,4\\}$. From the bow tie coloring
scheme, which is stated in Lemma 1, we may assume that
$c(u_{1}u_{2})=c(u_{3}u_{4})=5$. Without loss of generality we verify that
$u_{2}$ is a saturated vertex.

First we show that $u_{2}u_{3}\notin E(G)$, and with similar argument
$u_{2}u_{4}\notin E(G)$. Indeed, suppose for contradiction $u_{2}u_{3}\in
E(G).$ From the known colors of the $P_{5}$ path $u_{4}uu_{3}u_{2}u_{1}$,
$c(u_{3}u_{2})=4$. But this results a rainbow-$P_{5}$ path, namely
$u_{1}uu_{2}u_{3}u_{4}$, with edge-colors from left to right $1,\ 2,\ 4$ and
$5$ respectively.

Next suppose there is a vertex $w\in V(G)\backslash\\{u,u_{1},u_{3},u_{4}\\}$
such that $wu_{2}\in E(G)$. From the $P_{5}$ path $wu_{2}uu_{3}u_{4}$,
$c(wu_{2})\in\\{3,5\\}$. However, it can not be $5$, as $c(u_{1}u_{2})=5$ and
$u_{1}u_{2}$ is incident to the edge $wu_{2}$. This implies $c(wu_{1})=3$, but
this results a rainbow-$P_{5}$ $wu_{2}uu_{4}u_{3}$ with edge colors from left
to right $3,\ 2,\ 4$ and $5$ respectively. This completes the proof of Lemma
6. ∎

From Lemma 6 if $G$ contains a bow tie, then its degree-$2$ vertices are
saturated and hence we have two adjacent degree-$2$ vertices to finish the
proof by induction.

######  Lemma 7.

If $G$ contains four $3$-cycles sharing an edge, then each vertex of the
cycles is saturated.

###### Proof.

Let the four $3$-cycles be $uwu_{i}w$, where $i\in\\{1,2,3,4\\}$. Clearly $G$
contains a heavy-pair $uu_{i}w$, where $i\in\\{1,2,3,4\\}$.

From the heavy-pair coloring scheme given in Lemma 5, assume
$c(uu_{1})=c(wu_{2})=1$, $c(uu_{2})=c(wu_{1})=2$, $c(uu_{3})=c(wu_{4})=3$,
$c(uu_{4})=c(wu_{3})=4$ and $c(uw)=5$. Denote
$S=\\{u,w,u_{1},u_{2},u_{3},u_{4}\\}$.

Observe that no two vertices in $\\{u_{1},u_{2},u_{3},u_{4}\\}$ are adjacent.
Indeed, suppose $u_{1}u_{2}\in E(G)$. Clearly $(u_{1}u_{2}u,uwu_{3})$-bow tie
is a subgraph in $G$. From Lemma 6, $u_{1},u_{2},u_{3}$ and $w$ are saturated
vertices in $G$, which is not true and hence a contradiction.

Let $x\in V(G)\backslash S$. It can be shown that $x$ is not adjacent to any
vertex in $S$. To see this, suppose $xu\in E(G)$. From the $P_{5}$ paths
$xuu_{4}wu_{1},\ xuu_{4}wu_{2}$ and $xuu_{2}wu_{3}$, $c(xu)$ is respectively
in $\\{2,3\\}$, $\\{1,3\\}$ and $\\{1,4\\}$, which is a contradiction. For a
similar argument $xw\notin E(G)$.

Suppose $xu_{1}\in E(G).$ From the $P_{5}$ paths $xu_{1}wuu_{3},xu_{1}wuu_{4}$
and $xu_{1}wu_{3}u$ $c(xu_{1})$ is respectively in $\\{3,5\\}$, $\\{4,5\\}$
and $\\{3,4\\}$, which is again a contradiction. For similar reasons $xu_{2},\
xu_{3},\ xu_{4}\notin E(G)$. This completes the proof of Lemma 7. ∎

From Lemma 7 observe that if $G$ contains four $3$-cycles sharing an edge and
$S$ is the set of vertices of the cycles, then $G[S]$ is a $6$-vertex and
$9$-edge nice-component, and we can finish the proof by induction.

######  Lemma 8.

If $G$ contains three $3$-cycles sharing an edge, then $G$ contains either a
nice-component or a degree-$1$ vertex.

###### Proof.

Let the three $3$-cycles be $uwu_{i}u$, where $i\in\\{1,2,3\\}$. The cherries
$uu_{i}w$, where $i\in\\{1,2,3\\}$, form a medium-pair in $G$. Denote,
$S=\\{u,w,u_{1},u_{2},u_{3}\\}$. We distinguish two cases considering the
medium-pair coloring scheme stated in Lemma 3.

Case 1: The medium-pair is colored with the four-coloring scheme.

Without loss of generality assume $c(uw)=1$, $c(uu_{1})=c(wu_{2})=2$,
$c(uu_{2})=c(wu_{1})=3$, $c(uu_{3})=4$ and $c(wu_{3})=5$. Let $x\in
V(G)\backslash S$.

It can be checked that each vertex in $\\{u_{1},u_{2},u_{3}\\}$ is a saturated
vertex. For completeness, we show for $u_{1}$, but similar arguments can be
given to show for the rest. It is easy to check that both
$u_{1}u_{2},u_{1}u_{3}\notin E(G)$. Suppose $xu_{1}\in E(G).$ From the $P_{5}$
paths $xu_{1}wuu_{3}$, $xu_{1}uwu_{3}$ and $xu_{1}uu_{3}w$, $c(xu_{1})$ is in
$\\{1,4\\}$, $\\{1,5\\}$ and $\\{4,5\\}$ respectively, which is a
contradiction.

If both $u$ and $w$ are saturated vertices, then we are done as $G[S]$ is a
$5$-vertex and $7$-edge nice-component and we are done.

Without loss of generality assume $xu\in E(G)$. If $xw\notin E(G)$, it can be
checked that $d(x)=1$ and we are done. Indeed, from the $P_{5}$ paths
$xuu_{3}wu_{2}$ and $xuu_{3}wu_{1}$, we get $c(xu)=5$. Suppose for
contradiction $y\in N(x)\backslash\\{u\\}$. Observe that from the $P_{5}$
paths $yxuu_{2}w$, $yxuwu_{1}$ and $yxuwu_{2}$, $c(yx)$ is respectively in
$\\{2,3\\}$, $\\{1,3\\}$ and $\\{1,2\\}$, which is a contradiction.

On the other hand, if $xw\in E(G)$, then $uwu_{1}u,uwu_{2}u,uwu_{3}u$ and
$uwxu$ are four $3$-cycles sharing an edge. In this case we are done by Lemma
7, as $G[S\cup\\{x\\}]$ is a $6$-vertex and $9$-edge nice-component.

Case 2: The medium-pair is colored with three-coloring scheme.

Without loss of generality, let $c(uw)=1$, $c(uu_{1})=2$, $c(uu_{2})=3,\
c(uu_{3})=4,\ c(wu_{3})=2,\ c(wu_{2})=4$ and $c(wu_{1})=3$.

From the proof of Case 1 of Lemma 4, it is easy to see that both $u$ and $w$
are saturated vertices. Moreover, no two vertices in $\\{u_{1},u_{2},u_{3}\\}$
are adjacent. If each vertex in $\\{u_{1},u_{2},u_{3}\\}$ is a saturated, then
we are done as $G[S]$ is a $5$-vertex and $7$-edge nice-component.

Next we show that if there is $x\in V(G)\backslash S$ such that $xu_{i}\in
E(G)$, where $i\in\\{1,2,3\\}$, then $d(x)=1$ and we are done. To see this,
without loss of generality suppose $xu_{3}\in E(G)$. From the $P_{5}$ paths
$xu_{3}wu_{2}u$ and $xu_{3}wuu_{2}$, $c(xu_{3})\in\\{3,4\\}$ and
$c(xu_{3})\in\\{1,3\\}$ respectively. Thus, $c(xu_{3})=3$.

It can be checked that $xu_{2},xu_{1}\notin E(G)$. Indeed, suppose $xu_{2}\in
E(G).$ In this case we get $(u_{1}uw,wu_{2}xu_{3})$-fish, where edges of the
$4$-cycle are colored with at least three colors, namely $2,\ 3$ and $4$. But
this is a contradiction to the fish graph coloring scheme stated in Lemma 2.
Now suppose $y\in N(x)\backslash\\{u_{3}\\}$. From the $P_{5}$ paths
$yxu_{3}wu_{2}$, $yxu_{3}wu$ and $yxu_{3}uw$, $c(yx)$ is in $\\{2,4\\}$,
$\\{1,2\\}$ and $\\{1,4\\}$ respectively, which is again a contradiction. This
completes the proof of Lemma 8. ∎

######  Lemma 9.

Let $u$ and $w$ be two non adjacent vertices in $G$ such that $N(u)\cap
N(w)\neq\emptyset$ and $d(u)=4$. If $d(w)=3$, then $N(w)\subset N(u)$.

###### Proof.

Let $v\in N(u)\cap N(w)$ and suppose for contradiction, $w_{1}\in
N(w)\backslash N(u)$. This implies we have two vertices $u_{1}$ and $u_{2}$ in
$N(u)\backslash\\{v\\}$ but not in $N(w)$. Let $u_{3}$ and $w_{2}$ be the
remaining vertices in $N(u)$ and $N(w)$ respectively. Notice that the vertices
could be identical.

Let $c(uv)=1$ and $c(vw)=2$. For a clear reason, one of the edges in
$\\{uu_{1},uu_{2}\\}$ receives a color not in $\\{1,2\\}$. Without loss of
generality, assume that $c(uu_{1})=3$. Moreover, from the degree condition of
$u$, $c(uu^{*})=4$, which is a brand new color and
$u^{*}\in\\{u_{2},u_{3}\\}$. From the $P_{5}$ paths $w_{1}wvuu_{1}$, and
$w_{1}wvuu^{*}$, we have $c(ww_{1})=1$, and as a result $c(ww_{2})=3.$

If $u_{3}$ and $w_{2}$ are distinct vertices, we have a rainbow-$P_{5}$ path
$w_{2}wvuu^{*}$, where the edges color from left to right are respectively
$3,\ 2,\ 1$ and $4$.

On the other hand if $u_{3}$ and $w_{2}$ are identical vertices, both
$c(uw_{2})$ and $c(uu_{2})$ can not receive $1$ and $3$, as $uu_{1}$ and $uv$
already received these colors and are incident to the edges $uw_{2}$ and
$uu_{2}$. Therefore, we get a rainbow-$P_{5}$ path $w_{1}ww_{2}uu_{2}$, which
is a contradiction. This completes the proof of Lemma 9. ∎

######  Remark 1.

__

  1. (i)

It can be checked that if $d(w)=4$ in the assumptions of Lemma 9, then
$N(w)=N(u)$.

  2. (ii)

Observe that $G$ does not contain (as a subgraph) two non adjacent vertices
$u$ and $w$ such that $N(u)\cap N(w)\neq\emptyset$, and $d(u)\geq 5$ and
$d(w)\geq 3$. Indeed, suppose such a subgraph exists. Let
$\\{w_{1},w_{2},w_{3}\\}\subseteq N(w)$ and $w_{1}\in N(u)$. From the proof of
Lemma 9, $w_{2},w_{3}\in N(u)$ and $uw_{1}w,\ uw_{2}w$ and $uw_{3}w$ form a
medium-pair. Moreover, form the degree condition of $u$, $u$ is adjacent to at
least two vertices not in $\\{w_{1},w_{2},w_{3},w\\}$. From Lemma 4, $G$
contains a rainbow-$P_{5}$ which is a contradiction.

######  Lemma 10.

If $G$ contains two adjacent vertices $u$ and $w$ such that $d(u)\geq 5$ and
$d(w)\geq 4$, then $G$ contains either a degree-$1$ vertex or two adjacent
vertices of degree-$2$ or a nice-component.

###### Proof.

If $N(u)\cap N(w)\neq\emptyset$, then from Lemma 9, there are at least three
$3$-cycles sharing the edge $uw$, and we can finish the proof using Lemma 8.

Let $\\{u_{1},u_{2},u_{3},u_{4}\\}\subseteq N(u)\backslash\\{w\\}$. First we
verify that $d(u_{1})\leq 2$. Suppose for contradiction $d(u_{1})=3$. One can
see that $u_{1}$ is adjacent to no vertex in $\\{u_{2},u_{3},u_{4}\\}$.
Indeed, let $u_{1}u_{2}\in E(G)$. Since $u_{1}w\notin E(G)$, $N(u_{1})\cap
N(w)\neq\emptyset$ and $d(w)\geq 4$, by Lemma 9, $u_{2}\in N(w)$ and hence
$N(u)\cap N(w)\neq\emptyset$, which is a contradiction.

Let $x,y\in N(u_{1})$. From Lemma 9, $x,y\in N(w)$. Therefore, we get a
medium-pair $wuu_{1},wxu_{1}$ and $wyu_{1}$. Since $d(w)\geq 4$, there is a
vertex in $N(w)\backslash\\{u,x,y\\}$, say $w_{1}$. Clearly we have a four-
coloring scheme for the medium-pair and we have two coloring permutation of
the cherries. We check for the coloring $c(wy)=c(u_{1}x)=1,\
c(wx)=c(u_{1}y)=2,\ c(wu)=3$ and $c(uu_{1})=4$. Similar arguments could be
given for the other coloring permutation of the medium-pair. Let $u^{*}\in
N(u)\backslash\\{u_{1},w\\}$. Because of the $P_{5}$ path $u^{*}uwxu_{1}$,
$c(u^{*}u)\in\\{1,2\\}$. Thus from the color options and since $d(u)\geq 5$ it
is easy to find a rainbow-$P_{5}$ path which is a contradiction.

Now assume $d(u_{1})=2$ and $x\in N(u_{1})\backslash\\{w\\}$. It can be shown
that $d(x)\leq 2$, and with this we complete the proof. Indeed, for the reason
given above if $x\in N(u)$, then $d(x)=2$ and we get two adjacent degree-$2$
vertices $u_{1}$ and $x$, and hence we are done. Suppose that $d(x)\geq 3$.
Then by Remark 1 (ii), the graph contains a rainbow-$P_{5}$, which is a
contradiction. This completes the proof of Lemma 10. ∎

##  7 Avoiding some particular graph structures

In this section we do some further refinement by avoiding particular
structures where we can still finish the proof by induction. The following
theorems and results are important to doing so.

######  Theorem 8.

Let $u$ and $w$ be two non adjacent degree-4 vertices in $G$ such that
$N(u)\cap N(w)\neq\emptyset$. Then $G$ contains either a degree-$1$ vertex or
a nice-component.

###### Proof.

Denote $c(uu_{i})=i$, where $i\in\\{1,2,3,4\\}$. Denote also
$S=\\{u_{1},u_{2},u_{3},u_{4}\\}$ and $S^{\prime}=S\cup\\{u,w\\}$.

From Remark 1 (i), we may assume that $N(u)\cap
N(w)=\\{u_{1},u_{2},u_{3},u_{4}\\}$. Moreover, from the heavy-pair coloring
scheme without loss of generality we may assume that $c(wu_{4})=3,\
c(wu_{3})=4,\ c(wu_{2})=1$ and $c(wu_{1})=2$. We have two possible
arrangements of the colors as shown in Figure 6.

$1$$4$$2$$3$$2$$3$$1$$4$$u$$w$$u_{1}$$u_{2}$$u_{4}$$u_{3}$$u$$w$$1$$4$$3$$2$$2$$3$$4$$1$$u_{1}$$u_{3}$$u_{4}$$u_{2}$
Figure 6: Two possible edge-color arrangements of the heavy-pair.

We give the proof for the first color arrangement. But similar argument can be
given for the second color arrangement.

Clearly both $u$ and $w$ are saturated vertices. Let $x\in V(G)\backslash
S^{\prime}$ and $xu_{i}\in E(G)$, for some $i\in\\{1,2,3,4\\}$. There is no
vertex $y\in V(G)\backslash S^{\prime}\cup\\{x\\}$ such that $xy\in E(G)$.
Indeed, without loss of generality suppose $xu_{1}\in E(G)$. From the $P_{5}$
path $xu_{1}uu_{3}w$, $c(xu_{1})\in\\{3,4\\}$. Let $c(xu_{1})=3$. Then from
the $P_{5}$ paths $yxu_{1}uu_{2}$, $yxu_{1}uu_{4}$ and $yxu_{1}wu_{3}$,
$c(yx)$ is respectively in $\\{1,2\\}$, $\\{1,4\\}$ and $\\{2,4\\}$, which is
a contradiction. Similar arguments can be given if we assume that
$c(xu_{1})=4.$ Therefore, for each vertex $x\in V(G)\backslash S^{\prime}$
such that $xu_{i}\in E(G)$, $xu_{j}\in E(G)$ for some $j\neq i$, where
$i,j\in\\{1,2,3,4\\}$, otherwise we are done. Moreover, each vertex in $S$ is
with degree at most $4$.

If each vertex in $S$ is of degree-$2$, then $G[S^{\prime}]$ is a $6$-vertex
and $8$-edge nice-component and we are done. Moreover, only one edge in
$\\{u_{1}u_{2},u_{3}u_{4}\\}$ may exist in $G$ and both
$u_{1}u_{4},u_{2}u_{3}\notin E(G)$. Indeed, in the former case if both exist
we get a bow tie with one of its degree-$2$ vertex which is not saturated,
which is a contradiction. To verify the later case, suppose $u_{2}u_{3}\in
E(G)$. Then from the known edge colors of the $P_{5}$ path
$u_{2}u_{3}wu_{1}u$, $c(u_{2}u_{3})=1$, which is again a contradiction as
$wu_{2}$ is already colored with $1$ and yet incident to the edge
$u_{2}u_{3}$.

Suppose $u_{1}u_{2}\in E(G)$. Clearly $c(u_{1}u_{2})\in\\{3,4\\}$, and without
loss of generality assume $c(u_{1}u_{2})=3$. It can be checked that both
$u_{3}$ and $u_{4}$ are saturated vertices. To see this, suppose $u_{4}$ is
not saturated vertex and $x\in V(G)\backslash S^{\prime}$ such that $xu_{4}\in
E(G)$. From the $P_{5}$ paths $xu_{4}wu_{2}u,xu_{4}uu_{2}u_{1}$ and
$xu_{4}uu_{1}u_{2}$, $c(xu_{4})$ is in $\\{1,2\\},\\{2,3\\}$ and $\\{1,3\\}$
respectively which is a contradiction.

Next we show that if $u_{1}$ is not a saturated vertex, it is adjacent to a
degree-$1$ vertex. This also holds for $u_{2}$. To see this, let $xu_{1}\in
E(G)$. Clearly $c(xu_{1})=4$ and $xu_{4}\notin E(G)$, as $u_{4}$ is a
saturated vertex. If $xu_{2}\in E(G)$, then $c(xu_{2})\in\\{3,4\\}$. But both
colors are not possible as $u_{1}u_{2}$ and $u_{1}x$ are colored with $3$ and
$4$ and are incident to $xu_{2}$. Therefore, if such a vertex $x$ exist, then
$d(x)=1$, and we are done otherwise $G[S^{\prime}]$ is a $6$-vertex and
$9$-edge nice-component and we are done. We distinguish two cases depending on
the degrees of vertices in $S$.

Case 1: There is a degree-$4$ vertex in $S$.

Without loss of generality assume $d(u_{1})=4$ and $z_{1},z_{2}\in
V(G)\backslash S^{\prime}$ such that $z_{1}u_{1},z_{2}u_{1}\in E(G)$. From the
planarity of $G$ one of the following condition could happen.

  1. 1.

$\\{z_{1},z_{2}\\}\subset N(u_{2})$. From Lemma 9 it can be shown that each
vertex in $\\{z_{1},z_{2},u_{3},u_{4}\\}$ is saturated and therefore
$G[S^{\prime}\cup\\{z_{1},z_{2}\\}]$ is an $8$-vertex and $12$-edge nice-
component.

  2. 2.

$\\{z_{1},z_{2}\\}\subset N(u_{4})$. Again using Lemma 9 it can be verified
that each vertex in $\\{z_{1},z_{2},u_{2},u_{3}\\}$ is saturated and therefore
$G[S^{\prime}\cup\\{z_{1},z_{2}\\}]$ is an $8$-vertex and $12$-edge nice-
component.

  3. 3.

$z_{1}\in N(u_{2})$ and $z_{2}\in N(u_{4})$ or vice versa. In both cases using
Lemma 9, it can be shown that each vertex in
$\\{z_{1},z_{1},u_{2},u_{3},u_{4}\\}$ are saturated and hence
$G[S^{\prime}\cup\\{z_{1},z_{2}\\}]$ is an $8$-vertex and $12$-edge nice-
component.

Case 2: There is no degree-$4$ vertex in $S$.

Without loss of generality, assume $d(u_{1})=3$ and $z_{1}\in V(G)\backslash
S^{\prime}$ such that $z_{1}u_{1}\in E(G)$. Obviously
$c(z_{1}u_{1})\in\\{3,4\\}$. Let $c(z_{1}u_{1})=3$. Clearly either
$z_{1}u_{2}\in E(G)$ or $z_{1}u_{4}\in E(G)$, but not both due to the the
planarity of $G$.

We show the case when $z_{1}u_{2}\in E(G)$, and a similarly argument can be
given when $z_{1}u_{4}\in E(G)$. It is obvious that $c(z_{1}u_{2})=4$, and
$z_{1}$ is a saturated vertex. If both $u_{3}$ and $u_{4}$ are saturated
vertices, then $G[S^{\prime}\cup\\{z_{1}\\}]$ is a $7$-vertex and $10$-edge
nice-component and we are done. Otherwise, we have a cherry $u_{3}z_{2}u_{4}$
in $G$, where $z_{2}\in V(G)\backslash S^{\prime}$ and $c(u_{3}z_{1})=1$ and
$c(z_{1}u_{4})=2$ or vice versa. In this case $z_{2}$ is also a saturated
vertex and hence $G[S^{\prime}\cup\\{z_{1},z_{2}\\}]$ is an $8$-vertex and
$12$-edge nice-component and we are done. This completes the proof of Theorem
8. ∎

######  Definition 7.

A _double diamond_ is two $4$-cycles sharing exactly one vertex, see a double
diamond in Figure 7. We may describe the double diamond in the figure using
its vertices as $(u_{1}xu_{2}u,uu_{3}yu_{4})$-double diamond.

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u$$y$$x$ Figure 7: The double diamond.

######  Lemma 11.

Let $G$ contains $(u_{1}xu_{2}u,uu_{3}yu_{4})$-double diamond and
$S=\\{u_{1},u_{2},u_{3},u_{4},x,y\\}$. If there is a vertex $u_{1}^{\prime}\in
N(u_{1})\backslash S$ and $u_{2}^{\prime}\in N(u_{2})\backslash S$, then
$u_{1}^{\prime}$ and $u_{2}^{\prime}$ are identical vertices.

###### Proof.

Let the edge-coloring be $c$ and denote $c(uu_{i})=i$, where
$i\in\\{1,2,3,4\\}$. It is easy to show that $c(xu_{2})\in\\{1,3,4\\}$.
Suppose for contradiction $u_{1}^{\prime}$ and $u_{2}^{\prime}$ are distinct
vertices.

First, we assume $c(xu_{2})=1$. From the $P_{5}$ path $u_{1}xu_{2}uu_{3}$ and
$u_{1}xu_{2}uu_{4}$, $c(xu_{1})=2$. Clearly $c(yu_{3})\in\\{1,2\\}$ and
$c(yu_{4})\in\\{1,2\\}$. Without loss of generality assume $c(yu_{3})=1$ and
$c(yu_{4})=2$. With these colors we have $c(u_{1}u_{1}^{\prime})=4$ and
$c(u_{2}u_{2}^{\prime})=3$. However, we get a contradiction as
$u_{1}^{\prime}u_{1}uu_{2}u_{2}^{\prime}$ is a rainbow-$P_{5}$ path with edge
colors from left to right are respectively $4,\ 1,\ 2$ and $3$.

Next assume without loss of generality $c(xu_{2})=3$. With this $c(xu_{1})=4$.
It is easy to show that $c(u_{2}^{\prime}u_{2})\in\\{1,4\\}$. Let
$c(u_{2}^{\prime}u_{2})=1$. From the $P_{5}$ path
$u_{1}^{\prime}xu_{2}u_{2}^{\prime}$, $c(u_{1}^{\prime}u_{1})\in\\{1,3\\}$. It
can not be $1$ as $uu_{1}$ is an incident edge to $u_{1}^{\prime}u_{1}$ and
already received this color. Thus, $c(u_{1}^{\prime}u_{1})=3$. From the
$P_{5}$ path $yu_{3}uu_{2}u_{2}^{\prime}$ and $yu_{3}uu_{1}x$, we have
$c(yu_{3})=1$. This color and the known colors of the $P_{5}$ path
$u_{3}yu_{4}uu_{2}$ result $c(yu_{4})=2$. However we obtain a rainbow path
$yu_{4}uu_{1}u_{1}^{\prime}$, where edge colors from left to right are
respectively $2,\ 4,\ 1$ and $3$. A similar argument can be be given if we
assume that $c(u_{2}^{\prime}u_{2})=4$. ∎

######  Remark 2.

_Notice that from Lemma 11 if $u_{3}^{\prime}\in N(u_{3})\backslash S$ and
$u_{4}^{\prime}\in N(u_{4})\backslash S$ exist, then $u_{3}^{\prime}$ and
$u_{4}^{\prime}$ are identical vertices. Moreover, if the identical vertices
$u_{1}^{\prime}$ and $u_{2}^{\prime}$ exist (similarly $u_{3}^{\prime}$ and
$u_{4}^{\prime}$), then using the four-coloring scheme of the medium-pair it
can be seen that both $u_{3}^{\prime}$ and $u_{4}^{\prime}$ do not exist._

######  Theorem 9.

If $G$ contains a vertex of degree at least $5$, then $G$ contains either a
degree-$1$ vertex or two adjacent vertices of degree-$2$ or a nice-component.

###### Proof.

Let $u\in V(G)$ such that $d(u)\geq 5$. From Lemma 10, we may assume each
vertex in $N(u)$ is of degree at most $3$. Let
$S=\\{u_{1},u_{2},u_{3},u_{4},u_{5}\\}\subseteq N(u)$ and denote
$c(uu_{i})=i$, $i\in\\{1,2,\dots,5\\}$.

If $G[S]$ contains two independent edges, then we get a bow tie and we are
done. It can be checked that $0\leq e(G[S])\leq 3$. We finish the proof
considering cases on the existence of an edge in $G[S]$.

Case 1: $e(G[S])\neq 0$.

Suppose $e(G[S])=3$. Clearly the edges form a $3$-cycle. Without loss of
generality, assume $G[S]=\\{u_{1}u_{2},u_{1}u_{3},u_{2}u_{3}\\}$. The
vertices, $u_{1},u_{2}$ and $u_{3}$ are saturated vertices.

First we show that the vertices $u_{4}$ (similarly $u_{5}$) is a degree-$2$
vertex. In doing so if $u_{4}^{\prime}\in N(u_{4})\backslash\\{u\\}$, then by
Remark 1 (ii), $d(u_{4}^{\prime})=2$ and hence $u_{4}$ and $u_{4}^{\prime}$
are adjacent degree-$2$ vertices and we are done.

Suppose not and let $\\{u_{4}^{\prime},u_{4}^{\prime\prime}\\}\subset
N(u_{4})\backslash\\{u\\}$ and
$\\{u_{5}^{\prime},u_{5}^{\prime\prime}\\}\subset N(u_{5})\backslash\\{u\\}$.
If $c(u_{1}u_{2})=5$, then it is easy to check that $d(u_{4})=2$, which is a
contradiction. On the other hand if $c(u_{1}u_{2})\neq 5$, again it is easy to
check $d(u_{5})=2$, which is again a contradiction.

Case 2: $e(G[S])=0$.

For an obvious reason, we may assume that $d(u_{i})=3$ for each
$i\in\\{1,2,3,4,5\\}$. Let $S^{\prime}=\bigcup_{i=1}^{5}N(u_{i})$.

From Remark 2, $G[S^{\prime}]$ contains no double-diamond with a common vertex
$u$. In other words, if two $4$-cycles in $G[S^{\prime}]$ contain $u$, then
the cycles share an edge $uu_{i}$, for some $i\in\\{1,2,\dots,5\\}$. Moreover,
the number of $4$-cycles in $G[S^{\prime}]$ containing $u$ is at most $3$ and
this happens when the $4$-cycles share only three edges in
$\\{uu_{1},uu_{2},\dots,uu_{5}\\}$. In other words, at least two edges are not
contained in any $4$-cycle containing $u$. Without loss of generality, assume
the edges be $uu_{4}$ and $uu_{5}$.

Notice that $d(u_{4})=d(u_{5})=3$. Let
$N(u_{4})\backslash\\{u\\}=\\{u_{4}^{\prime},u_{4}^{\prime\prime}\\}$ and
$N(u_{5})\backslash\\{u\\}=\\{u_{5}^{\prime},u_{5}^{\prime\prime}\\}$. Clearly
$u_{4}^{\prime},\ u_{4}^{\prime\prime},\ u_{5}^{\prime}$ and
$u_{5}^{\prime\prime}$ are distinct vertices. It is easy verify that
$c(u_{4}^{\prime}u_{4})$ and $c(u_{4}^{\prime\prime}u_{4})$ are in $\\{5,r\\}$
and $c(u_{5}^{\prime}u_{5})$ and $c(u_{5}^{\prime\prime}u_{5})$ are in
$\\{4,r\\}$, where $r\neq 4,5$. Clearly we have a vertex
$u^{*}\in\\{u_{1},u_{2},u_{3}\\}$, such that $c(uu^{*})\notin\\{4,5,r\\}$.
Moreover, $d(u^{*})=1,$ which is a contradiction. This completes the proof of
Theorem 9. ∎

######  Theorem 10.

If $G$ contains two adjacent vertices $u$ and $w$ such that $N(u)\cap
N(w)\neq\emptyset$ and $d(u)=d(w)=4$, then $G$ contains either a degree-$1$
vertex or two adjacent vertices of degree-2 or a nice-component.

###### Proof.

Let $N(u)\backslash\\{w\\}=\\{u_{1},u_{2},u_{3}\\}$ and
$N(w)\backslash\\{u\\}=\\{w_{1},w_{2},w_{3}\\}$. If $|N(u)\cap N(w)|=3$, then
we are done by Lemma 8. Next we distinguish three cases depending on the size
of $N(u)\cap N(w)$.

Case 1: $|N(u)\cap N(w)|=2$.

Suppose $(u_{1},w_{1})$ and $(u_{2},w_{2})$ are identical pair of vertices.
Observe that $u_{3}\notin N(u_{1})$ and also $u_{3}\notin N(u_{2})$, otherwise
it is easy to find a bow tie with one of its degree-$2$ vertex which is not
saturated.

First we show $d(u_{3})\leq 2$. Indeed, suppose $d(u_{3})=3$. Since
$N(u_{3})\cap N(w)\neq\emptyset,$ and $d(w)=4$, then $N(u_{3})\subset N(w)$.
This implies, there is a vertex in $N(u_{3})\backslash\\{u\\}$ adjacent either
$u_{1}$ or $u_{2}$, but this is a contradiction.

Let $u_{3}^{\prime}\in N(u_{3})\backslash\\{u\\}$. Clearly
$u_{3}^{\prime}\notin N(u)$. Here we show that $d(u_{3}^{\prime})\leq 2$ and
finish the proof of this case. Suppose $d(u_{3}^{\prime})=3$. Since $N(u)\cap
N(u_{3}^{\prime})\neq\emptyset$ and $d(u)=4$, then $N(u_{3}^{\prime})\subset
N(u)$.

Observe that $N(u_{3}^{\prime})$ can not be $\\{w,u_{1}\\}$ or
$\\{w,u_{2}\\}$, because in both cases we create a bow tie. Thus,
$N(u_{3}^{\prime})=\\{u_{1},u_{2}\\}$. From this we get a medium-pair
$u_{3}^{\prime}u_{3}u,\ u_{3}^{\prime}u_{2}u$ and $u_{3}^{\prime}u_{1}u$.
Since $d(u)=4$, we must use four-coloring scheme for the medium-pair. For this
we have two coloring permutations for the cherries. Let the coloring be
$c(uu_{1})=c(u_{2}u_{3}^{\prime})=2,\ c(u_{1}u_{3}^{\prime})=c(uu_{2})=1,\
c(uu_{3})=3$ and $c(u_{3}u_{3}^{\prime})=4$. However this coloring results the
$4$-cycle of $(u_{1}wu,uu_{2}u_{3}^{\prime}u_{3})$-fish to receive at least
three colors, which is a contradiction to the coloring scheme of a fish graph.
Similar argument can be given for the other color permutation of the cherries.

Case 2: $|N(u)\cap N(w)|=1$.

Let $(u_{1},w_{1})$ be the identical pair of vertices, and
$c(u_{1}w)=1,c(u_{1}u)=2$ and $c(uw)=3$. Obviously one of the edge in
$\\{uu_{2},uu_{3}\\}$ must receive a brand new color. Let $c(uu_{2})=4$. From
the known colors of the $P_{5}$ path $w_{2}wu_{1}uu_{2}$,
$c(w_{2}w)\in\\{2,4\\}$. From the color options we have and $d(w)=4$, then we
may assume $c(ww_{2})=4$ and $c(ww_{3})=2$. Moreover, it can be seen that
$c(uu_{3})=1.$

Observe that $u_{2}\notin N(u_{3})$, otherwise get a bow tie. Also observe
that $u_{2}w_{2}\notin E(G)$. Indeed, suppose such an edge exists. From the
$P_{5}$ paths $u_{1}wuu_{2}w_{2},\ wu_{1}uu_{2}w_{2}$ and $u_{1}uww_{2}u_{2}$,
$c(u_{2}w_{2})$ is in $\\{1,3\\},\\{1,2\\}$ and $\\{2,3\\}$ respectively, and
this is a contradiction. In addition to these, it can be seen that
$u_{2}u_{1}\notin E(G)$. Indeed, suppose such an edge exist. From the $P_{5}$
path $w_{2}wuu_{1}u_{2}$, $c(u_{1}u_{2})\in\\{3,4\\}$. It can not be $4$
because of the incident edge $uu_{2}$ which is colored with 4. But this
results a rainbow-$P_{5}$ paths, namely $uu_{2}u_{1}ww_{3}$, where the edge
colors from left to right are respectively $4,3,1$ and $2$.

Suppose $x\in V(G)\backslash\\{w_{3}\\}$ such that $x\in N(u_{2})$. From the
$P_{5}$ paths $xu_{2}uu_{1}w,\ xu_{2}uwu_{1}$ and $xu_{2}uww_{3}$, $c(xu_{2})$
is in $\\{1,2\\},\\{1,3\\}$ and $\\{2,3\\}$, which is a contradiction. Thus if
$u_{2}w_{3}\notin E(G)$, then we are done as $d(u_{2})=1$. Notice that from
symmetry, what we have so far for $u_{2}$ hold for $w_{2}$ too.

To complete the proof, we assume that both $u_{2}w_{3},w_{2}u_{3}\in E(G)$.
Clearly $c(w_{3}u_{2})=1$ and $c(u_{3}w_{2})=2$. Observe that there is no
$x\in V(G)\backslash\\{u_{1},u_{3}\\}$ such that $xw_{3}\in E(G)$. Indeed,
suppose such a vertex and edge exist. Then from the $P_{5}$ paths
$xw_{3}u_{2}uu_{1},\ xw_{3}u_{2}uw$ and $xw_{3}wuu_{3}$, $c(xw_{3})$ is
respectively in $\\{2,4\\}$, $\\{3,4\\}$ and $\\{1,3\\}$, which is a
contradiction.

Let $x\in V(G)\backslash\\{u_{3},w_{3}\\}$ such that $xu_{1}\in E(G)$. From
the $P_{5}$ paths $xu_{1}wuu_{2}$ and $xu_{1}uu_{2}w_{3}$, we have
$c(xu_{1})=4$. Now we can show that $d(x)=1$ and we are done. Indeed, first
notice that $xw_{3},\ xu_{3},\ xu_{2},\ xw_{2}\notin E(G)$. Next, let $y\in
V(G)\backslash\\{u_{1}\\}$ and $yx\in E(G)$. Remember $y\notin N(u_{1})$,
otherwise we create a bow tie. From the $P_{5}$ paths $yxu_{1}uw,\ yxu_{1}wu$
and $yxu_{1}uu_{3}$, $c(yx)$ is respectively in $\\{2,3\\},\\{1,3\\}$ and
$\\{1,2\\}$, which is a contradiction.

Observe that if $w_{3}u_{1}\in E(G)$, then it can be shown that both
$u_{3}u_{1}$ and $w_{3}u_{3}$ are not in $E(G)$. Indeed, the former is true,
as otherwise a bow tie will be created. To show the latter case, suppose note
and $u_{3}w_{3}\in E(G)$. From the $P_{5}$ path $wuu_{1}w_{3}u_{2}$,
$c(u_{1}w_{3})=3$. Moreover, from the $P_{5}$ path $ww_{2}u_{3}w_{3}u_{2}$,
$c(u_{3}w_{3})=4$. But the colors result a rainbow-$P_{5}$ path
$wu_{1}w_{3}u_{3}w_{2}$, where the edge colors from left to right are
respectively $1,3,4$ and $2$. Therefore if $w_{3}u_{1}\in E(G)$, $u_{3}$ and
$w_{2}$ are adjacent degree-$2$ vertices and we are done. With similar
argument if $u_{3}u_{1}\in E(G)$, then $u_{2}$ and $w_{3}$ are adjacent
degree-$2$ vertices and we are done.

If both $u_{3}u_{1},w_{3}u_{1}\notin E(G)$, then we may assume that
$w_{3}u_{3}\in E(G)$. Otherwise, we have adjacent degree-2 vertices and we are
done. If such an edge exists, the graph induced by
$\\{u,w,u_{1},u_{2},u_{3},w_{2},w_{3}\\}$ is a $7$-vertex and $10$-edge nice-
component, see the graph in Figure 8 (left). This completes the proof of
Theorem 10. ∎

$2$$1$$3$$2$$1$$4$$4$$2$$1$$4$$u$$w$$u_{1}$$u_{3}$$w_{2}$$u_{2}$$w_{3}$

$3$$1$$2$$4$$3$$4$$2$$1$$2$$3$$4$$u_{3}$$u$$w$$w_{2}$$w_{1}$$w_{3}$$u_{1}$$u_{2}$

Figure 8: Possible subgraphs of $G$.

##  8 Further refinements and finalizing the proof

We need the following two theorems to complete our proof. Both theorem gives
an estimate of the number of degree-$2$ vertices in the neighbor or second
neighbor of a given degree-$4$ vertex.

######  Theorem 11.

If $G$ contains two adjacent vertices $u$ and $w$ such that $N(u)\cap
N(w)=\emptyset$ and $d(u)=d(w)=4$, then either there is a degree-$1$ vertex or
two adjacent degree-2 vertex or there are at least two degree-2 vertices in
$N(u)$ and at least two degree-2 vertices in $N(w)$.

###### Proof.

If two vertices in $N(u)$ or $N(w)$ are adjacent, it is easy to check that the
vertices are degree-$2$ vertices and we are done. Theorem 8, we may assume
that vertices $N(u)\backslash\\{w\\}$ and $N(w)\backslash\\{u\\}$ are with
degree at most $3$.

Let $N(u)\backslash\\{w\\}=\\{u_{1},u_{2},u_{3}\\}$ and
$N(w)\backslash\\{u\\}=\\{w_{1},w_{2},w_{3}\\}$. Suppose $u_{1}$ and $u_{2}$
be degree-$3$ vertices. It is enough to show that $G$ contains either a
degree-$1$ vertex or two adjacent-vertices of degree-$2$ or a nice-component.

For clear reasons $N(u_{1})\backslash\\{u\\}\subset\\{w_{1},w_{2},w_{3}\\}$
and $N(u_{2})\backslash\\{u\\}\subset\\{w_{1},w_{2},w_{3}\\}$. Without loss of
generality assume $N(u_{1})\backslash\\{u\\}=\\{w_{1},w_{2}\\}$ and
$N(u_{2})\backslash\\{u\\}=\\{u_{1},u_{3}\\}$. This creates a medium-pair
$uww_{1},uu_{1}w_{1}$ and $uu_{2}w_{1}$, see Figure 8 (right).

Since $d(u)=4$, we use the four-coloring scheme for the medium-pair. Consider
the coloring
$c(uu_{1})=c(ww_{1})=1,c(uw)=c(u_{1}w_{1})=2,c(uu_{2})=3,c(u_{2}w_{1})=4$ and
$c(uu_{3})=4$. It can be checked that $c(ww_{2})$ and $c(w_{2}u_{1})$ are in
$\\{3,4\\}$, and we may assume $c(u_{1}w_{2})=3$ and $c(ww_{2})=4$. From the
$P_{5}$ paths $w_{3}ww_{2}u_{1}u$ and $w_{3}ww_{2}u_{1}w_{1}$, $c(w_{3}w)=3$.
Again from the $P_{5}$ path $w_{1}u_{2}w_{3}wu$, $c(u_{2}w_{3})=2$.

Denote $S=\\{u,w,u_{1},u_{2},w_{1},w_{2},w_{3}\\}$. Suppose that there is
$x\in V(G)\backslash S$ such that $xu_{3}\in E(G)$. Then from the $P_{5}$
paths $xu_{3}uu_{1}w_{1},xu_{3}uu_{1}w_{2}$ and $xu_{3}uww_{3}$, $c(xu_{3})$
is in $\\{1,2\\},\ \\{1,3\\}$ and $\\{2,3\\}$ respectively, and this is a
contradiction. Therefore there is no vertex $x\in V(G)\backslash S$, which is
adjacent to $u_{3}$. But it is still possible that $u_{3}$ can be adjacent
with $w_{2}$ or $w_{3}$. However from the planarity of $G$ either $u_{3}w_{2}$
or $u_{3}w_{3}$, but not both, is in $G$. If both are not in $G$, then
$d(u_{3})=1$, and we are done. On the other hand, if one of the edges exists,
then it can be seen that $u_{3}$ is a saturated vertex and $G[S]$ is an
$8$-vertex and $12$-edge nice-component, and we are done. This completes the
proof of Theorem 11. ∎

######  Theorem 12.

Let $u$ be a degree-$4$ vertex in $G$ such that all its neighbors are with
degree at most $3$. Then there is a degree-$1$ vertex or at least two
degree-$2$ vertices in $N(u)\cup N_{2}(u)$.

###### Proof.

Let $N(u)=\\{u_{1},u_{2},u_{3},u_{4}\\}$. We distinguish the the following
three cases based on the $e(G[N(u)])$. Remember, we do not have two
independent edges in $G[N(u)]$. Otherwise, we $G$ contains a bow tie and we
are done. Notice that $0\leq e(G[N(u)])\leq 3$.

Case 1: $e(G[N(u)])=3$.

In this case, the edges form $3$-cycle. Considering the degree condition of
the neighbors of $u$, $G[N[u]]$ is a $K_{4}$ incident to an edge. Let the
$3$-cycle be $u_{1}u_{2}u_{3}u_{1}$.

Notice that $2\leq d(u_{4})\leq 3$. Let $x\in V(G)\backslash\\{u\\}$ such that
$xu_{4}\in E(G)$. Clearly $d(x)\leq 2$. Otherwise,
$N(x)\subset\\{u_{1},u_{2},u_{3}\\}$, which is a contradiction as the vertices
$u_{1},u_{2}$ and $u_{3}$ are already saturated from the degree condition of
neighbors of $u$. This completes the proof of Case 1.

Case 2: $e(G[N(u)])=2$.

Here the edges must be incident to each other, and let
$G[N(u)]=\\{u_{1}u_{2},u_{1}u_{3}\\}$. Clearly, $u_{1}$ is saturated and
$u_{4}u_{3},u_{4}u_{2}\notin E(G)$, as a bow tie with unsaturated degree-2
vertex will be created.

Suppose that $x\in N(u_{4})\backslash\\{u\\}$. One can show that $d(x)\leq 2$.
Suppose $d(x)=3$ and $N(x)\backslash\\{u_{4}\\}=\\{x_{2},x_{3}\\}$. By Lemma 9
and since $u_{1}$ is saturated, $\\{x_{1},x_{2}\\}=\\{u_{2},u_{3}\\}$. We may
assume $(x_{2},u_{2})$ and $(x_{3},u_{3})$ are identical pair of vertices. We
have two fish graphs $(u_{3}u_{1}u,uu_{2}xu_{4})$-fish and
$(u_{1}u_{2}u,uu_{3}xu_{4})$-fish. From the coloring scheme of the fish graph,
let the first fish graph is colored as $c(uu_{1})=1,\ c(uu_{3})=3,\
c(uu_{2})=c(u_{4}x)=2$ and $c(uu_{4})=c(xu_{2})=4$. With this the $4$-cycle of
the second fish graph takes at least $3$ colors and this violates the coloring
scheme of a fish graph.

Therefore, if $d(u_{4})=2$, then its neighbor other than $u$ should be a
degree-$2$ vertex, and we are done. Moreover if $d(u_{4})=3$, then the two
vertices in $N(u_{4})\backslash\\{u\\}$ are degree-$2$ vertices, and again we
are done. This completes the proof of Case 2.

Case 3: $e(G[N(u)])=1$.

Let $G[N(u)]=u_{1}u_{2}$. First we consider the case that there is $x\in
V(G)\backslash\\{u\\}$ such that $x\in N(u_{3})\cap N(u_{4})$. With this we
get $(u_{1}u_{2}u,uu_{3}xu_{4})$-fish, and from the fish-coloring scheme
assume $c(uu_{3})=c(xu_{4})=3,\ c(uu_{4})=c(xu_{3})=4,\ c(uu_{1})=1,\
c(uu_{2})=2$ and $c(u_{1}u_{2})=3$.

It is easy to check that $u_{4}$ is a saturated vertex, i.e., $d(u_{4})=2$.
Moreover, there is no vertex in $y\in V(G)\backslash\\{u_{1},u_{2}\\}$ such
that $yx\in E(G)$. If both $xu_{2},xu_{1}\notin E(G),$ then we are done, as
$\\{x,u_{4}\\}\subset N(u)\cup N_{2}(u)$. If both $xu_{2},xu_{1}\in E(G)$, it
can be checked that $u_{3}$ is a saturated vertex, and hence
$\\{u_{3},u_{4}\\}\subset N(u)\cup N_{2}(u)$.

Without loss of generality, suppose $xu_{2}\in E(G)$ and $xu_{1}\notin E(G)$.
If $u_{2}$ is saturated, then we are done, as $\\{u_{1},u_{4}\\}\subset
N(u)\cup N_{2}(u)$. We assume that there is $y\in V(G)\backslash\\{u,u_{2}\\}$
such that $yu_{1}\in E(G)$. From the $P_{5}$ paths $yu_{1}uu_{4}x$ and
$yu_{1}u_{2}xu_{3}$, $c(yu_{1})=4$. Now we verify that $d(y)\leq 2$. Indeed,
let $y^{\prime}\in V(G)\backslash\\{u_{1}\\}$ so that $y^{\prime}y\in E(G)$.
From the $P_{5}$ paths $y^{\prime}yu_{1}uu_{2}$ and $y^{\prime}yu_{1}u_{2}x$,
$c(y^{\prime}y)=1$. Therefore, from the color option $d(y)=2$ and moreover
$\\{y,u_{4}\\}\subset N(u)\cup N_{2}(u)$ and we are done.

To complete the proof we assume $N(u_{3})\cap N(u_{4})=\\{u\\}$. We may assume
that either $u_{3}$ or $u_{4}$ is a degree-$3$ vertex, otherwise we are done.

Let $d(u_{4})=3$ and $N(u_{4})\backslash\\{u\\}=\\{x,y\\}$. We complete the
proof by showing either $x$ or $y$ is a degree-$2$ vertex. Indeed, Suppose for
$d(x)=d(y)=3$. Considering the degree condition of the neighbors of $u$, it is
easy to check that $xy\notin E(G)$.

Let $N(x)\backslash\\{u_{4}\\}=\\{x_{1},x_{2}\\}$ and
$N(y)\backslash\\{u\\}=\\{y_{1},y_{2}\\}$. Observe that both
$\\{x_{1},x_{2}\\}$ and $\\{y_{1},y_{2}\\}$ are $\\{u_{1},u_{2}\\}$, since
$N(u_{4})\cap N(u_{3})=\\{u\\}$. But this force $d(u_{1})=4$ and $d(u_{2})=4$,
which is a contradiction to the assumption of the degree condition of the
neighbors of $u$. This completes the proof of Case 3.

Case 4: $e(G[N(u)])=0$.

Clearly there is a degree-$3$ vertex in $N(u)$, otherwise we are done. Let
$d(u_{1})=3$ and $x,y\in N(u_{1})\backslash\\{u\\}$. Since $e(G[N(u)])=0$,
both $x,y\notin N(u)$.

Suppose $x$ and $y$ are both degree-$3$ vertices. It can be checked that
$xy\notin E(G)$. Let $N(x)\backslash\\{u_{1}\\}=\\{x_{1},x_{2}\\}$ and
$N(y)\backslash\\{u_{1}\\}=\\{y_{1},y_{2}\\}$. Clearly
$N(u)=\\{x_{1},x_{2},y_{1},y_{2}\\}$. Without loss of generality assume that
$(x_{1},u_{2})$, $(x_{2},u_{3})$, $(y_{1},u_{3})$ and $(y_{2},u_{4})$ are the
identical pairs, see Figure 9.

Consider the medium-pair with cherries $uu_{1}x,uu_{2}x$ and $uu_{3}x$. Since
$d(u)=4$, we need to use the four-coloring scheme for the cherries. We have to
consider two possible coloring permutations to finish the proof. In both
cases, what we prove is $u_{2}$ and $u_{4}$ are degree-$2$ vertex or
otherwise, a vertex in $N(u_{2})\backslash\\{u,x\\}$ and
$N(u_{4})\backslash\\{u,y\\}$ is a degree-$1$ vertex.

Consider the four-coloring scheme given by $c(uu_{3})=c(u_{1}x)=1,\
c(u_{3}x)=c(uu_{1})=2,\ c(uu_{2})=3$ and $c(u_{2}x)=4$, as shown in the Figure
9 (left). Clearly $c(uu_{4})=4$ and $c(u_{1}y)$ and $c(u_{3}y)$ are
$\\{3,4\\}$. Without loss of generality, assume $c(u_{1}y)=3$ and
$c(yu_{3})=4$. From the $P_{5}$ path $u_{1}yu_{4}uu_{3}$, $c(yu_{4})=1$

Let $u_{2}$ is not a degree-2 vertex and $z\in N(u_{2})\backslash\\{u,x\\}$.
From the $P_{5}$ paths $zu_{2}xu_{3}u$ and $zu_{2}xu_{1}y$, $c(zu_{2})=1$. Let
again $z^{\prime}\in N(z)\backslash\\{u_{2}\\}$. From the planarity of $G$ and
the degree condition of neighbors of $u$, $z^{\prime}$ can not be any of the
vertex in $\\{x,y,u_{3},u_{4}\\}$. From the $P_{5}$ paths
$z^{\prime}zu_{2}xu_{3}$, $z^{\prime}zu_{2}uu_{1}$ and
$z^{\prime}zu_{2}uu_{4}$, $c(z^{\prime}z)$ is in $\\{2,4\\}$, $\\{2,3\\}$ and
$\\{3,4\\}$ which is a contradiction. Therefore, $d(z)=1$ and we are done.

Suppose $u_{4}$ is not a degree-$2$ vertex and let $t\in
N(u_{4})\backslash\\{u,y\\}$. From the $P_{5}$ paths, $tu_{4}uu_{3}x$ and
$tu_{4}yu_{1}u$, $c(tu_{4})=2$. Let $t^{\prime}\in N(t)\backslash\\{u_{4}\\}$.
From the $P_{5}$ paths $t^{\prime}tu_{4}yu_{1},t^{\prime}tu_{4}yu_{3}$ and
$t^{\prime}tu_{4}uu_{2}$, $c(t^{\prime}t)$ is in $\\{1,3\\},\\{1,4\\}$ and
$\\{3,4\\}$ respectively, which is a contradiction. Therefore, $d(t)=1$, and
we are done.

The other possible four coloring-scheme of the medium-pair is when
$c(uu_{1})=c(u_{2}x)=1,c(uu_{2})=c(uu_{2})=c(u_{1}x)=2,c(uu_{3})=3$ and
$c(u_{3}x)=4$, see Figure 9 (right). Clearly $c(u_{1}y)\in\\{3,4\\}$. Without
loss of generality assume $c(u_{1}y)=3$. From the $P_{5}$ path
$u_{2}xu_{3}yu_{1}$, $c(u_{3}y)=1$. From the $P_{5}$ path $u_{2}uu_{4}yu_{1}$,
$c(u_{4}y)=2$.

Let $u_{2}$ is not a degree-2 vertex and $z\in N(u_{2})\backslash\\{u,x\\}$.
From the $P_{5}$ paths $zu_{2}xu_{3}u$ and $zu_{2}xu_{1}y$, $c(zu_{2})=3$. Let
again $z^{\prime}\in N(z)\backslash\\{u_{2}\\}$. From the planarity of $G$ and
the degree condition of neighbors of $u$, $z^{\prime}$ can not be any of the
vertex in $\\{x,y,u_{3},u_{4}\\}$. From the $P_{5}$ paths
$z^{\prime}zu_{2}xu_{3}$, $z^{\prime}zu_{2}uu_{1}$ and
$z^{\prime}zu_{2}uu_{4}$, $c(z^{\prime}z)$ is in $\\{1,4\\}$, $\\{1,2\\}$ and
$\\{2,4\\}$ which is a contradiction. Therefore, $d(z)=1$ and we are done.

Suppose $u_{4}$ is not a degree-$2$ vertex and let $t\in
N(u_{4})\backslash\\{u,y\\}$. From the $P_{5}$ paths, $tu_{4}yu_{3}x$ and
$tu_{4}yu_{1}u$, $c(tu_{4})=1$. Let $t^{\prime}\in N(t)\backslash\\{u_{4}\\}$.
From the $P_{5}$ paths $t^{\prime}tu_{4}yu_{1},t^{\prime}tu_{4}uu_{2}$ and
$t^{\prime}tu_{4}uu_{3}$, $c(t^{\prime}t)$ is in $\\{2,3\\},\\{2,4\\}$ and
$\\{3,4\\}$ which is a contradiction. Therefore, $d(t)=1$, and we are done.

To finalize the proof of of Case 4, we may assume that that three vertices in
$N(u)$ are of degree-$3$, otherwise we are done. Suppose $u_{1},u_{2}$ and
$u_{3}$ be such vertices. From the previous argument at least one vertex in
$N(u_{1}),N(u_{2})$ and $N(u_{3})$ are degree at most $2$. If we have a
degree-$1$ vertex in one of the three sets, then we are done. Otherwise, we
have obviously two degree-$2$ vertex in $N(u_{1})\cup N(u_{2})\cup N(u_{3})$.
This completes the proof of Case 4. ∎

$3$$1$$2$$4$$3$$2$$1$$1$$4$$4$$u_{1}$$u$$u_{2}$$u_{3}$$u_{4}$$x$$y$

$3$$2$$1$$1$$2$$4$$3$$2$$4$$1$$u_{1}$$u$$u_{2}$$u_{3}$$u_{4}$$x$$y$

Figure 9: Possible subgraphs of $G$.

In completing the proof, from now on we consider $G$ as a rainbow-$P_{5}$-free
$n$-vertex connected planar containing no degree-$1$ vertex or two adjacent
degree-$2$ vertices. With these, we have the following remark.

######  Remark 3.

__

  1. (i)

From Theorem 9, each vertex in $G$ is of degree at most $4$, i.e.,
$\Delta(G)\leq 4$.

  2. (ii)

From Theorem 10, $G$ contains no two adjacent vertices $u$ and $w$ such that
$d(u)=d(w)=4$ and $N(u)\cap N(w)\neq\emptyset$.

  3. (iii)

From Theorem 8, $G$ contains no two non adjacent vertices $u$ and $w$ with
$N(u)\cap N(w)\neq\emptyset$ such that $d(u)=d(w)=4$.

We need the following two important observations.

  1. 1.

Let $w_{1}w_{2}\in E(G)$, where $d(w_{1})=d(w_{2})=4$ and $N(w_{1})\cup
N(w_{2})=\emptyset$. From Theorem 11, $N(w_{1})$ and $N(w_{2})$ contains two
degree-$2$ vertices each. It can be seen that for each degree-$2$ vertex $u$
in $N(w_{1})$ (similarly for degree-$2$ vertex in $N(w_{2})$), there is no
degree-$4$ vertex $w_{3}$, where $w_{3}\neq w_{2}$, such that $u\in
N_{2}(w_{3})$.

  2. 2.

Let $v$ be a degree-$2$ vertex and $v\in N(w_{1})\cup N_{2}(w_{1})$, where
$d(w_{1})=4$ and all its neighbors are with degree at most $3$. It is simple
check that there is at most one degree-$4$ vertex $w_{2}$ such that $v\in
N_{2}(w_{2})$.

Let $x$ be a degree-$4$ vertex and $y$ be a degree-$2$ vertex in $G$. Denote
$d_{x}$ as the number of degree-$2$ vertex in $N(x)\cup N_{2}(x)$ and denote
$e_{y}$ as the number of degree-$4$ vertex $w$ such that $y\in N(w)\cup
N_{2}(w)$. It can be checked that $d_{x}\leq 8$ and $e_{y}\leq 2$.

######  Definition 8.

We define a _new-degree_ function,
$\tilde{d}_{G}:V(G)\longrightarrow\mathbb{R}$, as follows:

$\tilde{d}_{G}(x)=\begin{cases}3\ \ \ \ \ \ \ \ \ \ \ \ \emph{if}\
d_{G}(x)=3,\\\ 4-{d_{x}}/{2}\ \ \ \emph{if}\ d_{G}(x)=4,\\\ 2+{e_{x}}/{2}\ \ \
\emph{if}\ d_{G}(x)=2.\end{cases}$

Clearly $\tilde{d}_{G}$ is well-defined and $\tilde{d}_{G}(x)\leq 3$ for each
vertex $x\in V(G)$. Thus, by the handshaking lemma,

$2e(G)=\sum\limits_{x\in V(G)}\tilde{d}_{G}(x)\leq 3n.$

Therefore, $e(G)\leq{3n}/{2}$ and this completes the proof of Theorem 7.

##  9 Conjectures and concluding remarks

We pose the following conjectures concerning sharp upper bound of the rainbow
planar Turán number of $P_{6}$ and $P_{7}$.

######  Conjecture 2.

For all $n$,

$2n-O(1)\leq\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{6})\leq 2n.$

######  Conjecture 3.

For all $n$,

${5n}/2-O(1)\leq\operatorname{ex}_{\mathcal{P}}^{*}(n,P_{7})\leq{5n}/{2}.$

The lower bound in Conjecture 2 can be realized by taking disjoint copies of
the octahedron. The graph is $4$-edge colorable and as a result
rainbow-$P_{6}$-free. On the other hand, the lower bound in Conjecture 3 can
be realized by taking disjoint copies of the icosahedron. It is easy to see
the graph is $5$-edge colorable and hence rainbow-$P_{7}$-free.

## Acknowledgments

Győri’s research was partially supported by the National Research, Development
and Innovation Office NKFIH, grants K132696, K116769, and K126853. Martin’s
research was partially supported by Simons Foundation grant #709641. Paulos’s
research was partially supported by National Research, Development and
Innovation Office NKFIH grant K5081, Simons Foundation grant and CEU Global
Teaching Fellowship Program grant.

Paulos would like to thank Győri, Martin and Iowa State University, Department
of Mathematics, for arranging and hosting his research visit during the course
of this work.

## Dedications

Paulos wants to dedicate this research work to all Ethiopian university
professors, who are under political repression by the current savage and
corrupted regime.

## References

  * [1] B. Ergemlidze, E. Győri, and A. Methuku, On the Rainbow Turán number of paths, _The Electronic Journal of Combinatorics_ , (2019) 26(1), P1.17.
  * [2] D. Gerbner, T. Mészáros, A. Methuku, and C. Palmer, Generalized rainbow Turán problems, _The Electronic Journal of Combinatorics_ , (2022) 29(2), P2.44.
  * [3] A. Halfpap, The rainbow Turán number of $P_{5}$, _arXiv:2210.03376_ , (2022).
  * [4] A. Halfpap and C. Palmer, Rainbow cycles versus rainbow paths, _Australasian Journal of Combinatorics_ , (2021) 81(1), 152–169.
  * [5] O. Janzer, Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles, _Israel Journal of Mathematics_ , https://doi.org/10.1007/s11856-022-2380-9, (2022).
  * [6] D. Johnston, C. Palmer, and A. Sarkar, Rainbow Turán problems for paths and forests of stars, _The Electronic Journal of Combinatorics_ , (2017) 24(1), 1–34.
  * [7] D. Johnston and P. Rombach, Lower bounds for rainbow Turán numbers of paths and other trees, _Australasian Journal of Combinatorics_ , (2020) 78(1), 61–72.
  * [8] P. Keevash, D. Mubayi, B. Sudakov, and J. Verstraëte, Rainbow Turán problems, _Combinatorics, Probability and Computing_ , (2007) 16, 109–126.


# Comprehensive Review of Performance Optimization Strategies for Serverless
Applications on AWS Lambda

Mohamed Lemine El Bechir  Dallas, TX, US
<EMAIL_ADDRESS>Cheikh Sad Bouh  Dallas, TX, US
<EMAIL_ADDRESS>Abobakr Shuwail  Kuala Lumpur, Malaysia
<EMAIL_ADDRESS>
###### Abstract

This review paper synthesizes the latest research on performance optimization
strategies for serverless applications deployed on AWS Lambda. By examining
recent studies, we highlight the challenges, solutions, and best practices for
enhancing the performance, cost-efficiency, and scalability of serverless
applications. The review covers a range of optimization techniques including
resource management, runtime selection, observability improvements, and
workload-aware operations.

###### Index Terms:

Serverless Computing, AWS Lambda, Performance Optimization, Resource
Management, Cost Efficiency, Observability

##  I Introduction

Serverless computing, particularly on platforms like AWS Lambda, offers a
highly scalable and cost-efficient solution for deploying applications. This
paper reviews recent research on optimizing the performance of serverless
applications on AWS Lambda, providing insights into various optimization
strategies and their practical implications.

Serverless architectures eliminate the need for managing servers, allowing
developers to focus on writing code. AWS Lambda is one of the leading
serverless platforms that automatically scales applications in response to
incoming requests, ensuring efficient resource utilization. However, the
inherent nature of serverless computing introduces several challenges that
need to be addressed to optimize performance.

##  II Literature Review

###  II-A Execution Challenges and Practical Solutions

Srivastava et al. (2023) discuss the inherent challenges in executing long-
running functions on AWS Lambda primarily due to the platform’s default
timeout constraints. The paper provides practical insights into addressing
these challenges, suggesting methods to optimize function execution and
improve overall application performance. The methodologies include leveraging
AWS Step Functions to break down long-running tasks and implementing custom
retry logic to handle failures efficiently [1].

To mitigate execution challenges, the use of asynchronous processing can also
be beneficial. By decoupling tasks and using message queues such as AWS SQS,
long-running operations can be handled more efficiently. This approach not
only helps in avoiding timeout issues but also improves the overall
responsiveness of the application.

###  II-B Predictive Models for Performance and Cost

Kumari, Sahoo, and Behera (2023) propose a workflow-aware analytical model
designed to predict the performance and cost of serverless execution on
platforms like AWS Lambda. Their methodology involves using historical
execution data to train the model, which can then predict response times and
costs with high accuracy (99.2% and 98.7%, respectively). This predictive
capability helps in planning and optimizing resource allocation [2].

Predictive models play a crucial role in resource planning and cost
management. By analyzing historical data and usage patterns, these models can
provide valuable insights into future resource requirements. This enables
organizations to allocate resources more efficiently, ensuring optimal
performance while minimizing costs.

###  II-C Workload-Aware Performance Optimization

Mahmoudi and Khazaei (2022) present an analytical model focused on optimizing
the performance and cost of serverless computing platforms. Their approach
involves workload-aware operations, where the model adjusts resource
allocation based on the nature and size of the workloads. This method aims to
balance cost and performance effectively, providing a simplified deployment
process and calculating essential metrics like average response time and cold
start probabilities [3].

Workload-aware optimization techniques are essential for handling varying
workloads efficiently. By dynamically adjusting resource allocation based on
real-time workload analysis, serverless applications can achieve better
performance and cost efficiency. This approach ensures that resources are
utilized optimally, avoiding both under-provisioning and over-provisioning.

###  II-D Resource Variability Exploitation

Ginzburg and Freedman (2020) explore the variability in resource performance
on AWS Lambda and other cloud FaaS platforms. By identifying better-performing
servers and exploiting resource variability, the authors demonstrate potential
cost savings of up to 13%. Their methodology involves continuous monitoring of
execution times and resource probing to select the most efficient servers [4].

Exploiting resource variability involves identifying and utilizing the most
efficient servers available at any given time. This can be achieved through
continuous monitoring and benchmarking of server performance. By selecting
better-performing servers, organizations can optimize both performance and
cost.

###  II-E Impact of Language Runtimes

Jackson and Clynch (2018) investigate the impact of different language
runtimes (Python, NodeJS, .NET Core) on the performance and cost of serverless
functions. Their study uses benchmarking tests to compare runtime performance
and cost-efficiency, concluding that Python offers superior results in both
aspects. This finding provides a clear recommendation for developers to
consider Python for serverless applications on AWS Lambda [5].

The choice of runtime can have a substantial impact on the performance and
cost of serverless applications. Python, being lightweight and efficient, is
often recommended for serverless functions due to its faster startup times and
lower resource consumption. However, the choice of runtime should also
consider the specific requirements and constraints of the application.

###  II-F Architectural Optimization Using AWS SAM

Balakrishna (2024) provides a detailed guide on using the AWS Serverless
Application Model (AWS SAM) for optimizing serverless applications. The paper
highlights the use of Application Load Balancer (ALB) path-based routing for
efficient handling of HTTP requests. The methodology includes practical steps
for setting up AWS SAM, configuring ALB, and deploying serverless REST APIs,
showcasing significant improvements in request handling and resource
management [6].

Architectural optimizations involve designing the application to leverage the
strengths of serverless computing. Using tools like AWS SAM and ALB,
developers can build highly scalable and efficient applications. Path-based
routing with ALB ensures that requests are routed to the appropriate function,
improving the overall efficiency and performance.

###  II-G Enhancing Observability

Balakrishna (2022) delves into AWS Lambda metrics and techniques to improve
observability in serverless applications. The paper outlines strategies such
as implementing custom logging using AWS CloudWatch for monitoring and setting
up alarms to detect and respond to performance issues. These enhancements
ensure better resource utilization and operational efficiency [7].

Observability is critical for maintaining the health and performance of
serverless applications. By implementing comprehensive logging and monitoring
strategies, developers can gain insights into the application’s behavior,
detect anomalies, and respond to issues promptly. AWS CloudWatch provides a
powerful toolset for enhancing observability in serverless environments.

###  II-H Dynamic Resource Configuration

Wen, Wang, and Liu (2022) introduce StepConf, a framework for automating
resource configuration in serverless function workflows on AWS Lambda.
StepConf optimizes memory size and considers parallelism to save costs while
meeting service level objectives, achieving up to 40.9% cost savings. The
framework’s methodology involves dynamic adjustment of resources based on
real-time workload analysis [8].

Dynamic resource configuration allows serverless applications to adapt to
changing workloads in real-time. By optimizing memory size and parallelism,
StepConf ensures that resources are allocated efficiently, reducing costs
while maintaining performance. This approach is particularly beneficial for
applications with fluctuating workloads.

###  II-I Cold Start Optimization

Wang and Huang (2021) investigate techniques to mitigate the impact of cold
starts in AWS Lambda. Their study evaluates different strategies, such as
provisioned concurrency and container reuse, to reduce the latency associated
with cold starts. They find that provisioned concurrency can significantly
improve response times for latency-sensitive applications [9].

###  II-J Energy Efficiency

Liu and Shen (2020) explore the energy efficiency of serverless computing
platforms. Their research focuses on the energy consumption of serverless
functions and proposes techniques to reduce energy usage through efficient
resource allocation and scheduling. They demonstrate that optimizing energy
efficiency can lead to cost savings and a reduced environmental impact [10].

###  II-K Security Considerations

Zhou et al. (2019) address security challenges in serverless computing. Their
study highlights common security vulnerabilities and provides best practices
for securing serverless applications. They emphasize the importance of
implementing robust access controls, encryption, and regular security audits
to protect serverless applications from threats [11].

###  II-L Benchmarking Serverless Platforms

Baldini et al. (2017) provide a comprehensive benchmarking framework for
evaluating the performance of different serverless platforms, including AWS
Lambda. Their benchmarks cover various aspects such as function invocation
latency, throughput, and scalability. The study helps developers compare
serverless platforms and make informed decisions based on performance metrics
[12].

###  II-M Serverless Orchestration

Lloyd et al. (2018) explore serverless orchestration using AWS Step Functions
and other orchestration tools. Their research demonstrates how complex
workflows can be efficiently managed and executed using serverless
orchestration, providing benefits such as fault tolerance and simplified error
handling [13].

###  II-N Cost Analysis of Serverless Applications

Adzic and Chatley (2017) conduct a detailed cost analysis of serverless
applications compared to traditional server-based architectures. Their study
examines the cost implications of different deployment models and identifies
scenarios where serverless computing offers significant cost advantages [14].

###  II-O Serverless Data Processing

Jonas et al. (2019) investigate the use of serverless computing for large-
scale data processing tasks. Their study highlights the advantages of using
serverless architectures for data-intensive applications, such as scalability
and cost-efficiency, and provides guidelines for designing serverless data
processing pipelines [15].

##  III Comparative Analysis

The studies reviewed provide a range of approaches to optimize serverless
applications on AWS Lambda. While Srivastava et al. focus on overcoming
execution constraints, Kumari et al. and Mahmoudi & Khazaei offer predictive
models for performance and cost optimization. Ginzburg & Freedman highlight
the potential of exploiting resource variability, and Jackson & Clynch provide
insights into the impact of language runtimes. Balakrishna’s works emphasize
architectural optimization and observability, and Wen et al. introduce dynamic
resource configuration through StepConf.

The comparative analysis reveals that each approach has its strengths and
limitations. Execution challenges can be mitigated through asynchronous
processing and workflow management. Predictive models offer valuable insights
for resource planning, while workload-aware optimization ensures efficient
resource utilization. Exploiting resource variability and choosing optimal
runtimes can further enhance performance and cost efficiency. Architectural
optimizations and enhanced observability are essential for maintaining the
health and scalability of serverless applications.

##  IV Practical Examples and Case Studies

###  IV-A AWS Step Functions for Long-Running Tasks

Implementing AWS Step Functions to manage complex workflows and long-running
processes can help in breaking down tasks into smaller, manageable units,
reducing the risk of hitting AWS Lambda’s timeout limits. For example, a video
processing application can use Step Functions to divide the processing task
into multiple steps, each handled by a separate Lambda function.

###  IV-B Cost Prediction Models

Using the predictive models proposed by Kumari et al., organizations can
better plan their resource allocation, ensuring optimal performance and cost
management. For instance, an e-commerce platform can use historical data to
predict traffic patterns during sales events, allowing for efficient scaling
of resources.

###  IV-C Resource Variability Management

By continuously monitoring execution times and leveraging Ginzburg &
Freedman’s approach, businesses can achieve significant cost savings by
selecting more efficient servers. An IoT data processing application can
benefit from this approach by dynamically selecting the best-performing
servers for data analysis tasks.

##  V Limitations and Future Research

The predictive models, while highly accurate, may not account for all
variables in a real-world environment, such as sudden traffic spikes or
unexpected workload changes. Future research should focus on integrating these
models with real-time analytics to adapt to changing conditions dynamically.
Additionally, workload-aware optimization methods must consider the potential
trade-offs between performance and cost, ensuring that the chosen strategies
align with business objectives.

Future research should also explore the integration of machine learning
techniques for predictive modeling and optimization. Machine learning models
can provide more accurate predictions and dynamic adjustments based on real-
time data, further enhancing the performance and cost efficiency of serverless
applications.

##  VI Architectural Optimizations Using AWS SAM

Balakrishna’s guide on using AWS SAM and ALB for serverless REST APIs provides
a comprehensive framework for architectural optimization. Practitioners should
follow the detailed steps outlined to configure their serverless applications,
ensuring efficient HTTP request handling and resource management.

Architectural optimizations should also consider the use of microservices
patterns and event-driven architectures. By decomposing applications into
smaller, independent services, developers can improve scalability and
maintainability. Event-driven architectures enable efficient communication
between services, further enhancing the performance of serverless
applications.

##  VII Enhancing Observability

Balakrishna’s recommendations for improving observability are crucial for
maintaining performance in serverless environments. Implementing custom
logging using AWS CloudWatch and setting up alarms can help detect and resolve
issues promptly, ensuring continuous performance optimization.

Enhanced observability should also include distributed tracing and real-time
monitoring. Distributed tracing provides visibility into the flow of requests
across different services, helping to identify performance bottlenecks and
optimize workflows. Real-time monitoring allows for proactive detection of
issues, ensuring that applications remain responsive and reliable.

##  VIII Recommendations for Practitioners

###  VIII-A Adopting Predictive Models

Utilize workflow-aware analytical models to predict performance and cost
accurately, aiding in better resource planning. Integrating machine learning
techniques can further enhance the accuracy of predictions.

###  VIII-B Leveraging Resource Variability

Implement continuous monitoring and resource probing to select the most
efficient servers, achieving cost savings. Automated tools can help streamline
this process, ensuring that the best-performing servers are always selected.

###  VIII-C Choosing Optimal Runtimes

Consider using Python for serverless functions due to its superior performance
and cost-efficiency. However, evaluate the specific requirements of your
application before selecting a runtime.

###  VIII-D Enhancing Observability

Implement comprehensive monitoring and logging strategies to maintain high
performance and operational efficiency. Use distributed tracing and real-time
monitoring to gain deeper insights into application behavior.

###  VIII-E Following Architectural Best Practices

Use AWS SAM and ALB for optimizing serverless REST APIs, ensuring efficient
handling of HTTP requests and resource management. Adopt microservices
patterns and event-driven architectures to enhance scalability and
maintainability.

##  IX Conclusion

This review highlights the advancements and strategies in optimizing
serverless applications on AWS Lambda. By addressing execution challenges,
utilizing predictive models, managing resource variability, and enhancing
observability, developers can significantly improve the performance and cost-
efficiency of their serverless applications. Future research should continue
to explore these areas, focusing on integrating these strategies into
comprehensive optimization frameworks.

## References

  * [1] S. Srivastava et al., ”Execution of Serverless Functions Lambda in AWS Serverless Environment,” International Journal of Recent Trends in Computing and Communication, vol. 11, no. 9, pp. 9014, 2023.
  * [2] A. Kumari, B. Sahoo, and R. Behera, ”Workflow Aware Analytical Model to Predict Performance and Cost of Serverless Execution,” Concurrency and Computation: Practice and Experience, vol. 35, no. 7, pp. 7743, 2023.
  * [3] N. Mahmoudi and H. Khazaei, ”Performance Modeling of Serverless Computing Platforms,” IEEE Transactions on Cloud Computing, vol. 10, no. 3, pp. 3373, 2022.
  * [4] S. Ginzburg and M. Freedman, ”Serverless Isn’t Server-Less: Measuring and Exploiting Resource Variability on Cloud FaaS Platforms,” ACM SIGCOMM, pp. 9880-0099, 2020.
  * [5] D. Jackson and G. Clynch, ”An Investigation of the Impact of Language Runtime on the Performance and Cost of Serverless Functions,” IEEE/ACM Utility and Cloud Computing Companion, pp. 00050, 2018.
  * [6] B. Balakrishna, ”Unveiling the AWS SAM Magic for Serverless Restful APIs: Architecting with ALB Path-Based Routing in AWS,” International Journal of Cloud Computing, vol. 13, no. 2, pp. 1734, 2024.
  * [7] B. Balakrishna, ”Optimizing Observability: A Deep Dive into AWS Lambda Metrics,” Journal of Advanced Information and Communications Technology, vol. 1, no. 1, pp. 160, 2022.
  * [8] Z. Wen, Y. Wang, and F. Liu, ”StepConf: SLO-Aware Dynamic Resource Configuration for Serverless Function Workflows,” IEEE INFOCOM, pp. 9696-9796, 2022.
  * [9] S. Wang and Q. Huang, ”Mitigating Cold Start in Serverless Computing: Provisioned Concurrency and Beyond,” ACM Transactions on Internet Technology, vol. 21, no. 3, pp. 42-51, 2021.
  * [10] J. Liu and Y. Shen, ”Energy Efficiency in Serverless Computing: A Study of AWS Lambda,” Journal of Cloud Computing, vol. 9, no. 1, pp. 110-121, 2020.
  * [11] F. Zhou, X. Wang, and Y. Zhang, ”Security Challenges and Solutions in Serverless Computing: A Survey,” IEEE Access, vol. 7, pp. 119252-119265, 2019.
  * [12] I. Baldini et al., ”Benchmarking Performance of Serverless Computing Frameworks,” IEEE International Conference on Cloud Engineering, pp. 116-127, 2017.
  * [13] W. Lloyd et al., ”Serverless Orchestration: Improving Fault Tolerance and Performance of Data Processing Workflows,” IEEE International Conference on Cloud Computing Technology and Science, pp. 96-105, 2018.
  * [14] N. Adzic and D. Chatley, ”Serverless Computing: Economic and Architectural Impact,” IEEE International Conference on Cloud Computing Technology and Science, pp. 142-149, 2017.
  * [15] E. Jonas et al., ”Cloud Programming Simplified: A Berkeley View on Serverless Computing,” IEEE Micro, vol. 39, no. 6, pp. 70-80, 2019.