# On $S$-packing coloring of 2-saturated
subcubic graphs

MAIDOUN MORTADA*

KALMA Laboratory, Faculty of Sciences
Lebanese University, Baalbek
Lebabon
maydoun.mortada@liu.edu.lb

OLIVIER TOGNI

LIB, Université de Bourgogn
Dijon, France

## Abstract

For a non-decreasing sequence of integers $(a_1, a_2, \dots, a_k)$, a graph $G$ is $(a_1, a_2, \dots, a_k)$-packing colorable if $V(G)$ can be partitioned into $k$ sub-sets $V_1, V_2, \dots, V_k$ such that the distance between any two distinct vertices $x, y \in V_i$ is at least $a_i + 1$, $1 \le i \le k$. Our paper studies the pack- ing coloring of subcubic graphs. Gastineau and Togni [Discrete Math. 339 (2016), 2461–2470] asked whether every subcubic graph except the Petersen graph is (1, 1, 2, 3)-packing colorable. An $i$-saturated subcubic graph $G$, $0 \le i \le 3$, is a subcubic graph such that each vertex of degree 3 in $G$ has at most $i$ neighbors of degree 3. We prove here that every 2-saturated subcubic graph is (1, 1, 2, 3)-packing colorable.

# 1 Introduction

All graphs considered here are simple, having no loops or multiple edges. For a graph $G$, the set of vertices of $G$ is denoted by $V(G)$ and its set of edges by $E(G)$. For a vertex $x$ in $G$, we denote by $N(x)$ the set of neighbors of $x$ and by $d(x)$ the number of its neighbors. We denote by $\Delta(G)$ the maximum degree of vertices in $G$ and by $\delta(G)$ the minimum degree. Let $H \subseteq V(G)$, we denote by $G[H]$ the subgraph induced

<footnote>* Also at: Basic and Applied Sciences Research, Al Maaref University, Beirut, Lebanon; and: Graph Theory and Operation Research, Department of Mathematics and Physics, Lebanese International University (LIU), Beirut, Lebanon.</footnote>
by $H$. For a path $P = x_1 \dots x_n$, we call $x_1$ and $x_n$ the ends of $P$, while each other vertex is called an interior vertex. A path $P$ in a graph $G$ is said to be maximal if $P$ is not a proper subpath of any other path in $G$. The length of a shortest path in $G$ joining two vertices $x$ and $y$ is the distance between $x$ and $y$ in $G$ and it is denoted by $\text{dist}(x, y)$.

A graph $G$ is said to be subcubic if $\Delta(G) \le 3$. Let $G$ be a subcubic graph. A vertex $x$ in $G$ is said to be an *i-vertex* if $d(x) = i$, $2 \le i \le 3$. A 3-vertex $x$ in $G$ is said to be a *heavy vertex* if all its neighbors are 3-vertices and it is said to be *i-saturated*, $0 \le i \le 2$, if $N(x)$ contains $i$ 3-vertices. In [12], the authors classified the subcubic graphs into four classes:

* A subcubic graph $G$ is said to be 0-saturated if any two 3-vertices in $G$ are not adjacent. This type is also called 3-irregular subcubic graph in [8, 16].

* A subcubic graph $G$ is said to be 1-saturated if every 3-vertex in $G$ is adjacent to at most one 3-vertex.

* A subcubic graph $G$ is said to be 2-saturated if every 3-vertex in $G$ is adjacent to at most two 3-vertices.

* A subcubic graph $G$ is said to be 3-saturated if $G$ contains at least one heavy vertex.

For the class of 3-saturated subcubic graphs, the authors in [12] consider, for $0 \le i \le 3$, the subclass of (3, i)-saturated subcubics graphs, which consists of the 3-saturated subcubic graphs such that every heavy vertex is adjacent to at most i heavy vertices.

If $(a_1, a_2, \dots, a_k)$ is a non-decreasing sequence of positive integers, then a graph $G$ is said to be $(a_1, a_2, \dots, a_k)$-packing colorable if $V(G)$ can be partitioned into $k$ subsets $V_1, V_2, \dots, V_k$ such that for every two distinct vertices $x$ and $y$ in $V_i$, $\text{dist}(x, y) > a_i$ for $1 \le i \le k$. The smallest $k$ such that $G$ is $(1, 2, \dots, k)$-packing colorable is called the *packing chromatic number* of $G$ and is denoted by $\chi_{\rho}(G)$. This parameter was introduced by Goddard et al. [7] under the name of broadcast chromatic number.

For a graph $G$, $S(G)$ denotes the graph obtained from $G$ by replacing each edge with a path of length two. Many papers [2, 4, 5, 6, 8, 9, 14] were dedicated to finding a bound of $\chi_{\rho}(G)$ and $\chi_{\rho}(S(G))$ for a subcubic graph $G$. Balogh, Kostochka and Liu [1] and Brešar and Ferme [3] independently proved that the packing chromatic number is not bounded on the class of subcubic graphs. Gastineau and Togni [8] asked whether $\chi_{\rho}(S(G)) \le 5$. Then Brešar, Klavžar, Rall, and Wash [6] conjectured that $\chi_{\rho}(S(G)) \le 5$ for every subcubic graph $G$. Gastineau and Togni [8] proved that in order for a subcubic graph $G$ to have $\chi_{\rho}(S(G)) \le 5$ it is enough for $G$ to be (1, 1, 2, 2)-packing colorable. In a recent (not yet published) paper [11], Liu, Zhang and Zhang proved that every subcubic graph is (1, 1, 2, 2, 3)-packing colorable, hence that $\chi_{\rho}(S(G)) \le 6$. Yang and Wu [16] proved that every 3-irregular subcubic graph is (1, 1, 3)-packing colorable, and then a simpler proof for the same result was presented in [13]. Moreover, Brešar, et al. [6] proved that if $G$ is a generalized prism of a cycle,
then $G$ is (1, 1, 2, 2)-packing colorable if and only if $G$ is not the Petersen graph. Liu, Liu, Rolek and Yu [10] proved that subcubic graphs with maximum average degree less than $\frac{30}{11}$ are (1, 1, 2, 2)-packing colorable. Moreover, Tarhini and Togni [15] proved that every cubic Halin graph is (1, 1, 2, 3)-packing colorable. Finally, Mortada and Togni [12] recently proved that every 1-saturated subcubic graph is (1, 1, 2)-packing colorable and every (3, 0)-saturated subcubic graph is (1, 1, 2, 2)-packing colorable.

The technique used to prove our latest result [12] seems powerful as it allows us to prove that every 2-saturated subcubic graph is (1, 1, 2, 3)-packing colorable. The technique is based on considering an independent set in a 2-saturated subcubic graph $G$ that maximizes, among all independent sets, a linear combination of the number of 3-vertices with two neighbors of degree 3, the number of 3-vertices with one neighbor of degree 3, the number of 3-vertices with no neighbor of degree 3, and the number of 2-vertices. Considering such an independent set allows us to determine the distance between a sufficient number of vertices in $G$, leading at the end to the desired packing coloring of $G$.

## 2 Every 2-saturated subcubic graph is (1, 1, 2, 3)-packing colorable

**Theorem 2.1.** Every 2-saturated subcubic graph is (1, 1, 2, 3)-packing colorable.

*Proof.* On the contrary, suppose that $G$ is a counterexample with the minimum order $n$. Clearly, $G$ is connected. First, $\delta(G) \ge 2$, since otherwise, let $u$ be a vertex of degree 1 and let $G' = G - u$. By the minimality of $G$, $G'$ has a (1, 1, 2, 3)-coloring. Either $1_a$ or $1_b$ is not the color of the unique neighbor of $u$ in $G'$, then give this color to $u$, and so we obtain a (1, 1, 2, 3)-coloring of $G$, a contradiction.

Our plan is to partition the set of vertices of $G$ into four subsets on which two of them are independent, any two vertices in the third are at distance at least three while the distance is at least four between any two vertices in the fourth subset. The existence of such a partition proves that $G$ is (1, 1, 2, 3)-packing colorable, which is a contradiction. To reach this partition, we will first consider a special independent set that will lead to determining the distance between specific vertices in $G$.

Note that if $H$ is a subgraph of $G$ or a subset of $V(G)$ and if $x$ is a vertex in $H$, by saying $x$ is an $i$-vertex, we mean that $x$ is an $i$-vertex in $G$, $2 \le i \le 3$. That is, maybe $x$ does not have $i$ neighbors in $H$ but has them in $G$. Consequently, when we say $x$ is $i$-saturated, we mean that $x$ is $i$-saturated in $G$. Moreover, by saying $u$ is an $i$-neighbor of $v$, we mean that $u$ is a neighbor of $v$ and $u$ is an $i$-vertex, $2 \le i \le 3$.

Let $T$ be an independent set in $G$, and for $0 \le i \le 2$, let $X_i(T)$ be the set of 3-vertices in $T$ such that each of these vertices is $i$-saturated. Let $Y(T)$ be the set of 2-vertices in $T$. The set $V(G) \setminus T$ will be denoted by $\bar{T}$. Let us define $\phi(T) = |X_2(T)| + 0.9|X_1(T)| + 0.6|X_0(T)| + 0.4|Y(T)|$. The coefficients have been chosen to describe how important a vertex is for the independent set (e.g., a vertex in $X_1(T)$ is more important than two vertices in $Y(T)$ and a vertex in $X_2$ is less
important than two vertices in $X_0$). An independent set $T$ is said to be a maximum weighted independent set if $\phi(T) \ge \phi(K)$ for every independent set $K$. Let $S$ be a maximum weighted independent set.

Clearly, by the maximality of $\phi(S)$, each vertex in $\bar{S}$ has a neighbor in $S$. Thus, any interior vertex of a path in $G[\bar{S}]$ is a 3-vertex. Moreover, we have the following observation:

**Remark 2.1.** If $u$ is a 3-vertex in $\bar{S}$ such that $u$ has a 3-neighbor in $\bar{S}$, then $u$ has a 3-neighbor in $S$. Indeed, suppose to the contrary that $u$ has no 3-neighbor in $S$; then $S' = (S \setminus N(u)) \cup \{u\}$ is an independent set with $\phi(S') \ge \phi(S) + 0.1$ since each neighbor of $u$ in $S$ is in $Y(S)$ while $u \in X_2(S') \cup X_1(S')$, a contradiction.

Thus, since $G$ is 2-saturated, we can deduce that a path in $G[\bar{S}]$, where all of its vertices are 3-vertices, is of length at most one. Moreover, since each 2-vertex in $\bar{S}$ has a neighbor in $S$, $G[\bar{S}]$ contains neither a cycle nor a path where all vertices are 2-vertices and of length greater than one. Consequently, one can easily notice that there are only seven types of maximal paths in $G[\bar{S}]$ (see Figure 1):

* A maximal path of length zero, and this type will be denoted by $P_0$.

* A maximal path of length one and its vertices are 2-vertices, and this type will be denoted by $P_1$.

* A maximal path of length one and its vertices are a 2-vertex and a 3-vertex, and this type will be denoted by $P_2$.

* A maximal path of length one and its vertices are 3-vertices, and this type will be denoted by $P_3$.

* A maximal path of length two on which its ends are 2-vertices, and this type will be denoted by $P_4$.

* A maximal path of length two on which its ends are a 2-vertex and a 3-vertex, and this type will be denoted by $P_5$.

* A maximal path of length three on which its ends are 2-vertices, and this type will be denoted by $P_6$.

<figure><img src="image_1.png" /><figcaption>Figure 1: The different types of maximal paths in $G[\bar{S}]$.</figcaption></figure>

The coloring procedure will be to color the vertices of $S$ by a color $1_a$, and as much as possible, vertices of $\bar{S}$ by a color $1_b$ in such a way that there will remain one uncolored
vertex for each maximal path of type $\mathcal{P}_1$ to $\mathcal{P}_5$ and two for paths of type $\mathcal{P}_6$. We are going to use colors 2 and 3 for these vertices. However, we will also recolor some of the vertices of $S$ in order to have more flexibility to complete the coloring of the vertices of $\bar{S}$ and then we will also use the color $1_a$ in coloring particular vertices of $\bar{S}$.

**Remark 2.2.** Any two vertices in $\bar{S}$ not on the same maximal path in $G[\bar{S}]$ are not adjacent. In addition, an interior vertex of any maximal path in $G[\bar{S}]$ is a 3-vertex.

For a maximum weighted independent set $T$, we denote by $\theta(T)$ the number of maximal paths of type $\mathcal{P}_3$ in $G[\bar{T}]$. We will assume our maximum weighted independent set $S$ was chosen such that $\theta(S) \le \theta(T)$ for every maximum weighted independent set $T$.

A 2-vertex in $\bar{S}$ is said to be a *bad* 2-vertex if it is a vertex of any maximal path of type different from $\mathcal{P}_0$ in $G[\bar{S}]$. A 3-vertex in $\bar{S}$ is said to be a *bad* 3-vertex if it is a vertex on a maximal path in $G[\bar{S}]$ except those that are on a maximal path of type $\mathcal{P}_0$, those that are on a maximal path of type $\mathcal{P}_2$, and those that are ends of a maximal path of type $\mathcal{P}_5$. A bad 3-vertex is said to be a *weak bad* vertex if it is on a path of type $\mathcal{P}_3$, *mid bad* vertex if it is an interior vertex on a path of type $\mathcal{P}_4$ or $\mathcal{P}_5$, and *rough bad* vertex if it is on a path of type $\mathcal{P}_6$. We remark that if $x$ is a weak bad vertex, then $x$ has a unique neighbor in $G[\bar{S}]$ and this neighbor is a 3-vertex, and if $x$ is a mid bad vertex or rough bad vertex then $x$ has two neighbors in $G[\bar{S}]$. For abbreviation, when we say bad vertex, we mean that the vertex is either a bad 2-vertex or a bad 3-vertex.

A vertex $x \in S$ is said to be a *father* of a vertex $y \in \bar{S}$ if $x$ and $y$ are adjacent. Two non-adjacent vertices $u$ and $v$ in $\bar{S}$ are said to be *siblings* if they have a common father. In this case, we say $u$ is a sibling of $v$. Moreover, we say $u$ is a *bad sibling* of $v$ if $u$ is a bad vertex.

Since each sibling of a vertex $u$ is at distance less than three from $u$, we found it is important to count the number of bad siblings of each bad vertex. We have the following result:

**Claim 2.1.1.** 1. Each rough bad vertex and mid bad vertex has no bad sibling.

2. Each bad 2-vertex has at most one bad sibling.

3. Each weak bad vertex has at most one bad sibling.

4. Let $u$ be a 3-vertex in $\bar{S}$ such that $u$ is an end of a maximal path of type $\mathcal{P}_5$. Then $u$ is not a sibling of $v$ whenever $v$ is a rough bad vertex or a mid bad vertex. Besides, $u$ is not a sibling of $v$, whenever $v$ is a bad 2-vertex having a bad sibling.

*Proof.* **1.** Let $u$ be a rough bad vertex or a mid bad vertex. Note that $u$ has only one neighbor in $S$ since it has two neighbors in $\bar{S}$. Let $x$ be the father of $u$. Then $x$ is a 3-vertex since otherwise $S' = (S \setminus \{x\}) \cup \{u\}$ is an independent set with $\phi(S') > \phi(S)$, a contradiction. Suppose to the contrary that $u$ has a bad sibling $v$. In what follows,
we will consider the set $S' = (S \setminus N(v)) \cup \{u, v\}$. Clearly, $v$ is neither a rough bad vertex nor a mid bad vertex, since otherwise both $u$ and $v$ have a unique neighbor in $S$, which is $x$, and so $\phi(S') > \phi(S)$, a contradiction. Suppose first that $u$ is on a maximal path of type $\mathcal{P}_5$ or $\mathcal{P}_6$, which implies that $u$ is 2-saturated. Clearly, if $v$ has a neighbor in $S$, distinct from $x$, then $v$ is a weak bad vertex and this neighbor is a 2-vertex since $v$ already has two 3-neighbors: $x$ and its neighbor on the maximal path to which $v$ belongs in $G[\bar{S}]$. In this case, $x, u$ and $v$ are 2-saturated, and then $\phi(S') = \phi(S) + 0.6$, a contradiction. On the other hand, if $v$ is a 2-vertex, then $x$ is either 1- or 2-saturated and in either case, $\phi(S') \ge \phi(S) + 0.4$, a contradiction. Finally, suppose that $u$ is on a path of type $\mathcal{P}_4$, which implies that $u$ is 1-saturated. As before, if $v$ is a 3-vertex, then its neighbor in $S$ which is distinct from $x$ is a 2-vertex. In this case, $x$ and $v$ are 2-saturated and then we get $\phi(S') = \phi(S) + 0.5$. On the other hand, if $v$ is a 2-vertex, then regardless whether $x$ is 1- or 2-saturated, we have $\phi(S') \ge \phi(S) + 0.3$.

2. Let $u$ be a bad 2-vertex and suppose that $u$ has two bad siblings $v$ and $w$. By (1), $v$ ($w$, respectively) is either a bad 2-vertex or a weak bad vertex. Since $u$ has only one neighbor in $S$, then $u, v$ and $w$ have a common father in $S$, say $x$. In what follows, we will consider the set $S' = (S \setminus (N(v) \cup N(w))) \cup \{u, v, w\}$. Note that if $v$ is a weak bad vertex, then the neighbor of $v$ in $S$, which is distinct from $x$, is a 2-neighbor since $v$ already has two 3-neighbors: $x$ and its 3-neighbor on the maximal path to which $v$ belongs in $G[\bar{S}]$. We have the same situation for $w$. First of all, if both $v$ and $w$ are bad 2-vertices, then $x \in X_0(S)$ and so $\phi(S') = \phi(S) + 0.6$, a contradiction. For the case when $v$ is a weak bad vertex and $w$ is a bad 2-vertex, we have $x \in X_1(S)$ while $v \in X_2(S')$ and so $\phi(S') = \phi(S) + 0.5$, a contradiction. For the case when both $v$ and $w$ are weak bad vertices, we have $x \in X_2(S)$ while $v, w \in X_2(S')$, and so $\phi(S') = \phi(S) + 0.6$, a contradiction.

3. Let $u$ be a weak bad vertex and suppose that $u$ has two bad siblings, $v$ and $w$. By (1), each of $v$ and $w$ can be either a bad 2-vertex or a weak bad vertex only. First, we will study the case when $u, v$ and $w$ have a common father, say $x$. Then, in this case, $v$ and $w$ are both weak bad vertices by (2). Consequently, $x$ is a heavy vertex, a contradiction.

For the other case, let $x$ be the common father of $u$ and $v$ and $y$ be that of $u$ and $w$. In what follows, we will consider the independent set $S' = (S \setminus (N(v) \cup N(w))) \cup \{u, v, w\}$. Since $u$ is a weak bad vertex and $G$ is 2-saturated, then exactly one of $x$ and $y$ is a 2-vertex and the other a 3-vertex by Remark 2.1. Without loss of generality, assume that $y$ is the 3-vertex. If $v$ and $w$ are both bad 2-vertices, then $\phi(S') \ge \phi(S) + 0.4$, a contradiction. If $v$ and $w$ are weak bad vertices, then, by Remark 2.1, $v$ and $w$ are 2-saturated from which it follows that $\phi(S') \ge \phi(S) + 0.2$, a contradiction. Hence, we only need to consider the case that exactly one of $v$ and $w$ is a bad 2-vertex and the other a weak bad vertex. If $w$ is the weak bad vertex, then the other neighbor of $w$ in $S$, other than $y$, is a 2-vertex and we have $\phi(S') \ge \phi(S) + 0.6$, a contradiction. On the other hand, if $w$ is a bad 2-vertex and $v$ is a weak bad vertex, then the neighbor of $v$ in $S$ other than $x$, call it $z$, is a 3-vertex by Remark 2.1. If $z$ or $y$ is not 2-saturated, then we have $\phi(S') \ge \phi(S) + 0.1$, a
contradiction. Therefore, we may assume that both $y$ and $z$ are 2-saturated, and then we get $\phi(S') = \phi(S)$ but $\theta(S') < \theta(S)$, a contradiction. In fact, the maximal path to which $u$ ($v$, respectively) belongs in $G[\bar{S}]$ is of type $\mathcal{P}_3$, while the maximal path to which $z$ belongs in $G[\bar{S}']$ is not of type $\mathcal{P}_3$ since $z$ has two neighbors in $\bar{S}'$ and this implies that $\theta(S') \le \theta(S) - 1$.

4. Note that $u$ has a unique neighbor in $\bar{S}$ which is a 3-vertex and on the path of type $\mathcal{P}_5$ to which $u$ belongs. Suppose that $u$ is a sibling of a bad vertex $v$ and let $x$ be the common father of $u$ and $v$. If $v$ is a rough bad vertex or a mid bad vertex, then $x$ is a 3-vertex as proved in (1). Consequently, the neighbor of $u$, other than $x$, in $S$ is a 2-vertex and so $S' = (S \setminus N(u)) \cup \{u, v\}$ is an independent set with $\phi(S') = \phi(S) + 0.6$ if $v$ is 2-saturated and $\phi(S') = \phi(S) + 0.5$ if $v$ is 1-saturated, a contradiction. If $v$ is a bad 2-vertex having a bad sibling, say $w$, then $x$ is a common father of $u$, $v$ and $w$ and so $x$ is a 3-vertex. Consequently, a neighbor of $u$ in $S$, other than $x$, is a 2-vertex. Similarly, if $w$ is a weak bad vertex, then a neighbor of $w$ in $S$, other than $x$, is a 2-vertex. Hence, $S' = (S \setminus N(u) \cup N(w)) \cup \{u, v, w\}$ is an independent set with $\phi(S') = \phi(S) + 0.6$ if $w$ is a weak bad vertex and $\phi(S') = \phi(S) + 0.5$ if $w$ is a bad 2-vertex, a contradiction. $\square$

Let $B$ be a subset of bad vertices of $\bar{S}$ such that:

1. Each vertex in $B$ is either a bad 2-vertex on a maximal path of type $\mathcal{P}_1$ or $\mathcal{P}_2$, or a weak bad vertex.

2. For each maximal path $P$ in $G[\bar{S}]$ of type $\mathcal{P}_1$, $\mathcal{P}_2$ or $\mathcal{P}_3$, we have $|P \cap B| = 1$.

We define $B_S$ to be a subset of $B$ such that each vertex in $B_S$ has a sibling in $B$, and so each vertex in $B \setminus B_S$ has no sibling in $B$. Note that by Claim 2.1.1 (2) and (3), a vertex in $S$ can be adjacent to at most two vertices in $B_S$. A bad father in $S$ is a common father of two vertices in $B_S$. A bad father is said to be bad 2-father if it is a father of two bad 2-vertices in $B_S$, a bad 3-father if it is a father of two bad 3-vertices in $B_S$ and a bad mixed father if it is a father of a bad 2-vertex and a bad 3-vertex in $B_S$. See Figure 2 for an illustration of the sets $B$ and $B_S$ and of bad fathers.

We remark that any bad 3-father is a 2-vertex. Indeed, let $x$ be a bad 3-father and let $u$ and $v$ be the two bad 3-vertices with father $x$. Suppose that $x$ is a 3-vertex; then, since $G$ is 2-saturated, the neighbor of $u$ ($v$, respectively) in $S$ which is distinct from $x$ is a 2-vertex. Consequently, $S' = (S \setminus (N(u) \cup N(v))) \cup \{u, v\}$, is an independent set with $\phi(S') = \phi(S) + 0.2$, a contradiction. Here is the last step before defining the partition of $V(G)$:

**Claim 2.1.2.** We have $\text{dist}(x, y) > 2$ whenever $x$ and $y$ satisfy one of the following:

1. Both $x$ and $y$ are in $B \setminus B_S$.

2. Both $x$ and $y$ are bad 2-fathers.

3. Both $x$ and $y$ are 3-vertices in $B_S$ such that $x$ is not a sibling of $y$.

4. Both $x$ and $y$ are mid bad vertices or rough bad vertices that are not on the same maximal path.
<figure><img src="image_2.png" /><figcaption>Figure 2: The content of sets $B$ and $B_S$, and associated bad fathers in $S$, where numbers inside vertices are their degrees and bmf stands for bad mixed father, b3f for bad 3-father, and b2f for bad 2-father.</figcaption></figure>

**Proof. 1.** By the definition of $B$, $x$ and $y$ are not adjacent. Also, by the definition of $B_S$, $x$ and $y$ have no common father. Thus, $\text{dist}(x, y) > 2$.

2. Let $x$ and $y$ be two bad 2-fathers. Let $x_1$ and $x_2$ ($y_1$ and $y_2$, respectively) be the bad neighbors of $x$ ($y$, respectively). By Claim 2.1.1 (2), $x$ and $y$ have no common bad neighbor. We still need to prove that $x$ and $y$ have no common neighbor. Suppose that $x$ and $y$ have a common neighbor, say $u$. By Claim 2.1.1 (2), $u$ is not a bad vertex. Clearly, $x$ and $y$ are 3-vertices and $x$ and $y$ are not in $X_2(S)$. Note that if $u$ has a neighbor in $S$, distinct from $x$ and $y$, then it is a 2-vertex. We will study now two cases according to the neighbors of $u$ in $\bar{S}$. If $N(u) \cap \{x_1, x_2, y_1, y_2\} = \emptyset$, we get $S' = (S \setminus N(u)) \cup (N(x) \cup N(y))$ is an independent set with $\phi(S') = \phi(S) + 0.8$ if $u$ is a 2-vertex and $\phi(S') = \phi(S) + 0.4$ otherwise, a contradiction. We need now to consider the case that $N(u) \cap \{x_1, x_2, y_1, y_2\} \neq \emptyset$. Since $u$ is not a bad and $u$ has a neighbor in $\{x_1, x_2, y_1, y_2\}$, then $u$ is a vertex on a path of type $\mathcal{P}_2$ and its unique neighbor in $\bar{S}$ is one of the vertices in $\{x_1, x_2, y_1, y_2\}$. Without loss of generality, suppose $x_1$ is a neighbor of $u$, we get $S' = (S \setminus N(u)) \cup (\{x_2\} \cup N(y))$ is an independent set with $\phi(S') = \phi(S) + 0.4$, a contradiction. Consequently, $\text{dist}(x, y) > 2$.

3. By the definition of $x$, $y$, $B$ and $B_S$, and by Claim 2.1.1 (3), $x$ and $y$ are neither adjacent nor having a common neighbor and so $\text{dist}(x, y) > 2$.

4. By Claim 2.1.1 (1), $x$ and $y$ are not siblings, and since they are not on the same maximal path, then we reach the desired result. $\square$

**Claim 2.1.3.** We have $\text{dist}(x, y) > 3$ whenever $x$ and $y$ satisfy one of the following:

1. Both $x$ and $y$ are weak bad vertices in $B_S$ but $x$ is not a sibling of $y$ and the sibling of each of them in $B_S$ is also a 3-vertex.

2. Both $x$ and $y$ are rough bad vertices such that $x$ and $y$ are not on the same maximal path.

3. Both $x$ and $y$ are bad mixed fathers.
**Proof. 1.** By the definition of $B$ and by Claim 2.1.2 (3), $\text{dist}(x, y) > 2$. Let $x'$ be the bad 3-father of $x$ and $y'$ be that of $y$. We proved before that any bad 3-father is a 2-vertex, and so both $x'$ and $y'$ are 2-vertices. Then, $x'(y', \text{respectively})$ cannot have a common neighbor with $y$ ($x$, respectively). Let $x''(y'', \text{respectively})$ be the neighbor in $S$ of $x$ (resp $y$) distinct from $x'(y', \text{respectively})$. We must prove that $x''(y'')$, respectively) can't have a common neighbor with $y$ ($x$, respectively). By Remark 2.1, $x''$ and $y''$ are both 3-vertices. Suppose to the contrary that $x''$ and $y$ have a common neighbor, say $u$. Then, clearly, $u$ is the bad neighbor of $y$ in $\bar{S}$. As $y$ is a weak bad vertex, then $u$ is a 3-vertex. Note that $u$ has at most one 3-neighbor in $S$. We get $S' = (S \setminus (N(x) \cup N(u))) \cup \{x, u\}$, is an independent set with $\phi(S') > \phi(S)$, a contradiction. Similarly, we can prove $y''$ and $x$ have no common neighbor. Hence, $\text{dist}(x, y) > 3$.

2. By Claim 2.1.1 (1), each of $x$ and $y$ cannot have a bad sibling and since both neighbors of $x$ ($y$, respectively) in $\bar{S}$ are bad, then $\text{dist}(x, y) > 3$.

3. Let $x_1$ and $x_2$ be the bad neighbors of $x$ in $B_S$ and let $y_1$ and $y_2$ be that of $y$. Suppose $x_1$ ($y_1$, respectively) is a weak bad 3-vertex, and $x_2$ ($y_2$, respectively) is a bad 2-vertex. By definition of $x$ and $y$ and by Claim 2.1.1 (2) and (3), we have $\{x_1, x_2\} \cap \{y_1, y_2\} = \emptyset$. Besides, $x$ ($y$, respectively) has no common neighbor with any of the bad neighbors of $y$ ($x$, respectively). In fact, suppose $x$ has a common neighbor with a bad neighbor of $y$, say $u$, then, by Claim 2.1.1 (2) and (3), $u$ is not a bad vertex and so $u$ is a 3-vertex on a path of type $\mathcal{P}_2$ whose other end is $y_2$. We will consider now the independent set $S' = (S \setminus (N(x_1) \cup N(u))) \cup \{x_1, x_2, u\}$. If $u$ is 1-saturated, we get $\phi(S') = \phi(S) + 0.5$, a contradiction. If $u$ is 2-saturated, let $z$ be the neighbor of $u$ in $S$ other than $x$. As $u$ is 2-saturated then $z$ is a 3-vertex. Now, if $z$ is not 2-saturated, we get $\phi(S') \ge \phi(S) + 0.1$, a contradiction. Else, we get $\phi(S') = \phi(S)$ but $\theta(S') < \theta(S)$ since $x_1$ is on a path of type $\mathcal{P}_3$ in $G[\bar{S}]$ but $x$ is an isolated vertex in $G[\bar{S}']$ and $z$ has two neighbors in $G[\bar{S}']$, a contradiction. In the same way, we can show that $y$ has no common neighbor with any of the bad neighbors of $x$. We need to prove now that $x$ and $y$ have no common neighbor. Remark that if $x$ ($y$, respectively) has a third neighbor, then this neighbor is not bad. Suppose $x$ and $y$ have a common neighbor, say $u$. Then both $x$ and $y$ are 3-vertices, and if $u$ or any of the bad neighbors of $x$ and $y$ has a neighbor in $S$ distinct from both $x$ and $y$, then this neighbor is a 2-vertex. However, we get $S' = (S \setminus (N(u) \cup N(x_1) \cup N(x_2) \cup N(y_1) \cup N(y_2))) \cup (N(x) \cup N(y))$ is an independent set with $\phi(S') = \phi(S) + 0.6$ despite whether $u$ is a 2-vertex or 3-vertex, a contradiction. Consequently, $\text{dist}(x, y) > 3$. $\square$

Now, we are ready to define the sets $V_1, V_2, V_3$ and $V_4$ such that $V_1, V_2, V_3$ and $V_4$ form a partition of $V(G)$ satisfying the desired properties.

We will start with $V_1$ that contains:

1. each vertex in $B \setminus B_S$;

2. each mid bad vertex;

3. each bad 2-father;

4. one and only one rough bad vertex from each maximal path $P$ of type $\mathcal{P}_6$;
5. each weak bad vertex in $B_S$ whose sibling in $B_S$ is a 2-vertex;

6. exactly one of the vertices $x$ and $y$, whenever $x$ and $y$ are two weak bad vertices in $B_S$ with $x$ is a sibling of $y$.

On the other hand, $V_2$ contains:

1. each bad mixed father;

2. each rough bad vertex which is not in $V_1$;

3. each weak bad vertex in $B_S$ which is not in $V_1$.

Finally, $V_3$ contains every vertex in $S$ but not in $V_1 \cup V_2$, and every bad 2-vertex in $B_S$. At last, $V_4$ contains every remaining vertex, i.e. every vertex in $\bar{S}$ which is not in $V_1 \cup V_2 \cup V_3$.

<figure><img src="image_3.png" /><figcaption>Figure 3: Partition of the vertices corresponding with a (1, 1, 2, 3)-packing coloring (numbers inside vertices represent their degrees).</figcaption></figure>

Note that $V_3$ is an independent set. Actually, by definition of $B$, each two bad 2-vertices in $B_S$ are not adjacent. Moreover, any other two vertices in $S \cap V_3$ are not adjacent. Besides, any bad 2-father and bad mixed father is not in $V_3$.

As well, $V_4$ is an independent set. In fact, if $x$ and $y$ are two vertices in $V_4$, then either $x$ and $y$ are not on the same maximal path or $x$ and $y$ are ends of a maximal path of type $P_4$, $P_5$ or $P_6$. Consequently, $x$ and $y$ are not adjacent.

Concerning $V_1$ and $V_2$, we have the following two results:

**Claim 2.1.4.** The distance between any two vertices in $V_1$ is at least three.

*Proof.* Let $x$ and $y$ be two vertices in $V_1$. By Claim 2.1.2, $\text{dist}(x, y) > 2$ whenever $x$ and $y$ are of the same nature. Suppose that $x$ and $y$ are not of the same nature. If $x$ is a mid bad vertex and $y$ is a rough bad vertex, then the result follows from Claim 2.1.2 (4). We are left with the following cases:

1. $x$ is a vertex in $B \setminus B_S$.

Using the fact that $x$ is a bad vertex that has no sibling in $B$ and using Claim 2.1.1, we get $\text{dist}(x, y) > 2$ for any $y$.
2. $x$ is a mid bad vertex or a rough bad vertex but $y$ is not a vertex in $B \setminus B_S$.

If $y$ is a bad 2-father, then, by Claim 2.1.1 (1) and (4), $y$ is neither adjacent to $x$ nor to any neighbor of $x$ in $\bar{S}$ and so $\text{dist}(x, y) > 2$. For the case when $y$ is a weak bad vertex in $B_S$, the result follows from Claim 2.1.1 (1).

3. $x$ is a weak bad 3-vertex and $y$ is a 2-father.

Since $x$ is a weak bad vertex and $y$ is a bad 2-father, then $x$ and $y$ are not adjacent, and $x$ and $y$ have no common neighbor by Claim 2.1.1 (2).

□

**Claim 2.1.5.** The distance between any two vertices in $V_2$ is at least four.

*Proof*. First, note that the sibling of each weak bad vertex in $V_2$ is a weak bad vertex in $B_S \setminus V_2$. Let $x$ and $y$ be two vertices in $V_2$. If $x$ and $y$ are of the same nature, then the result follows from Claim 2.1.3. Thus, we need to prove the result when $x$ and $y$ are not of the same nature:

**1. $x$ is a rough bad vertex.**

If $y$ is a bad mixed father, then by Claim 2.1.1, $y$ cannot be a father of $x$ nor of any of the bad neighbors of $x$. Let $x'$ be the father of $x$ and let $y_1$ and $y_2$ be the bad neighbors of $y$ such that $y_1$ is a 3-vertex and $y_2$ is a 2-vertex. By Claim 2.1.1 (1), $x'$ cannot be a father of $y_1$ ($y_2$, respectively). We need to prove that $x'$ and $y$ have no common neighbor. Suppose to the contrary that $x'$ and $y$ have a common neighbor, say $u$. By Claim 2.1.1 (1), $u$ is not any of the bad neighbors of $y$ and so $y$ is a 3-vertex and the neighbor of $y_1$ in $S$, distinct from $y$, is a 2-vertex. Moreover, we have seen before that $x'$ is a 3-vertex, and so if $u$ has a neighbor in $S$ distinct from $x'$ and $y$ then this neighbor is a 2-vertex. Despite whether $x'$ is 1- or 2-saturated, we get $\phi(S') \ge \phi(S) + 0.5$ if $u$ is a 2-vertex and $\phi(S') = \phi(S) + 0.6$ otherwise, where $S' = (S \setminus (N(u) \cup N(y_1))) \cup \{x, u, y_1, y_2\}$ is an independent set, a contradiction. For the remaining case, that is if $y$ is a weak bad vertex, then by Claim 2.1.1 (1) and (3), $x$ is not a sibling of $y$, and the father of $x$ ($y$, respectively) cannot be a father of the bad neighbor of $y$ ($x$, respectively). Accordingly, for both cases of $y$, we have $\text{dist}(x, y) > 3$.

**2. $x$ is a weak bad vertex.**

We need to prove the result only when $y$ is a bad mixed father. By definition of $x$ and $y$ and by Claim 2.1.1, $y$ cannot be a father of $x$ and $y$ cannot be a father of the sibling of $x$. Moreover, by Claim 2.1.1 (2) and (3), $y$ cannot be a father of the bad neighbor of $x$. Let $x'$ be a father of $x$. We need to prove that $x'$ and $y$ have no common neighbor. If $x'$ is the bad 3-father of $x$, then, by a previous remark, $x'$ is a 2-vertex, and so the result follows. Otherwise, $x'$ is a 3-vertex by Remark 2.1. Suppose that $x'$ and $y$ have a common neighbor, say $u$. Clearly, $u$ is not a bad vertex by Claim 2.1.1 (3). Let $y_1$ and $y_2$ be the bad neighbors of $y$ such that $y_1$ is a 3-vertex and let $z$ be the neighbor of $y_1$ other than $y$. Then, $z$ is a 2-vertex. Besides, if $u$ has a neighbor in $S$ distinct from $x'$ and $y$, then this neighbor is a 2-vertex. Moreover,
if $u$ is a 2-vertex, then $y$ is 1-saturated while we already have $y_1$ is 2-saturated. Let $S' = (S \setminus (N(u) \cup N(x) \cup N(y_1))) \cup (\{x\} \cup N(y))$, then $S'$ is an independent set with $\phi(S') \ge \phi(S)+0.1$ if $u$ is a 2-vertex and $\phi(S') \ge \phi(S)+0.2$ otherwise, a contradiction. Consequently, $\text{dist}(x, y) > 3$. $\square$

Color the vertices of $V_1$ by 2, that of $V_2$ by 3, that of $V_3$ by $1_a$ and finally the vertices of $V_4$ by $1_b$ and so we obtain a (1, 1, 2, 3)-packing coloring of $G$, a contradiction. $\square$

### 3 Concluding Remarks

The result of Theorem 2.1 is tight in some sense since there are 2-saturated subcubic graphs that are not (1, 1, 3, 3)-colorable. Figure 4 presents such a graph. This graph is of diameter 3, and in each of the three triangles, (at most) two vertices can be given a 1-color. Hence, the remaining three vertices cannot be colored with the two colors 3. However, this graph is (1, 1, 2, 4)-colorable. Moreover, we could not find a non (1, 1, 2, 4)-colorable 2-saturated subcubic graph. Thus, we propose the following problems.

<figure><img src="image_4.png" /><figcaption>Figure 4: An example of a 2-saturated non (1, 1, 3, 3)-colorable subcubic graph. As can be seen, this graph is (1, 1, 2, 4)-colorable.</figcaption></figure>

**Open problem 1:** Is every 2-saturated subcubic graph (1, 1, 2, 4)-packing colorable?

**Open problem 2:** Is every 2-saturated subcubic graph (1, 2⁴)-packing colorable?

### Acknowledgements

We would like to thank the reviewers for taking the time and effort necessary to review the manuscript. We appreciate their valuable comments and suggestions, which helped us improve the manuscript's quality.
References

[1] J. Balogh, A. Kostochka and X. Liu, Packing chromatic number of cubic graphs, *Discrete Math.* 341(2) (2018), 474–483.

[2] J. Balogh, A. Kostochka and X. Liu, Packing Chromatic Number of Subdivisions of Cubic Graphs, *Graphs Combin.* 35(2) (2019), 513–537.

[3] B. Brešar and J. Ferme, An infinite family of subcubic graphs with unbounded packing chromatic number, *Discrete Math.* 341(8) (2018), 2337–2342.

[4] B. Brešar, N. Gastineau and O. Togni, Packing colorings of subcubic outerplanar graphs, *Aequationes Math.* 94(5) (2020), 945–967.

[5] B. Brešar, S. Klavžar, D. F. Rall and K. Wash, Packing chromatic number under local changes in a graph, *Discrete Math.* 340 (2017), 1110–1115.

[6] B. Brešar, S. Klavžar, D. F. Rall and K. Wash, Packing chromatic number, (1, 1, 2, 2)-colorings, and characterizing the Petersen graph, *Aequationes Math.* 91 (2017), 169–184.

[7] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris and D. F. Rall, Broadcast chromatic numbers of graphs, *Ars Combin.* 86 (2008), 33–49.

[8] N. Gastineau and O. Togni, S-packing colorings of cubic graphs, *Discrete Math.* 339 (2016), 2461–2470.

[9] D. Laiche, I. Bouchemakh and É. Sopena, Packing coloring of some undirected and oriented coronae graphs, *Discuss. Math. Graph Theory* 37(3) (2017), 66–690.

[10] R. Liu, X. Liu, M. Rolek and G. Yu, Packing (1, 1, 2, 2)-coloring of some subcubic graphs, *Discrete Applied Math.* 283 (2020), 626–630.

[11] X. Liu, X. Zhang and Y. Zhang, Every subcubic graph is packing (1, 1, 2, 2, 3)-colorable, arXiv 2404.09337 (2024).

[12] M. Mortada and O. Togni, About S-Packing Coloring of Subcubic Graphs, *Discrete Math.* 347(5) (2024), 113917.

[13] M. Mortada, About S-packing coloring of 3-irregular subcubic graphs, *Discrete Applied Math.* 359 (2024), 16–18.

[14] C. Sloper, An eccentric coloring of trees, *Australas. J. Combin.* 29 (2004), 30–321.

[15] B. Tarhini and O. Togni, S-Packing Coloring of Cubic Halin Graphs, *Discrete Applied Math.* 349(31) (2024), 53–58.

[16] W. Yang and B. Wu, On packing S-colorings of subcubic graphs, *Discrete Applied Math.* 334 (2023), 1–14.