# On b-greedy colourings and z-colourings

Jonas Costa Ferreira da Silva<sup>a,b</sup>, Frédéric Havet<sup>b,*</sup>

<figure><img src="image_1.png" /></figure>

Check for
updates

## ARTICLE INFO

**Article history:**

Received 5 January 2023

Received in revised form 18 July 2024

Accepted 3 August 2024

Available online 17 August 2024

**Keywords:**

Greedy colouring

b-colouring

z-colouring

Cubic graph

NP-hardness

## ABSTRACT

A b-greedy colouring is a colouring which is both a b-colouring and a greedy colouring. A z-colouring is a b-greedy colouring such that a b-vertex of the largest colour is adjacent to a b-vertex of every other colour. The b-Grundy number (resp. z-number) of a graph is the maximum number of colours in a b-greedy colouring (resp. z-colouring) of it. In this paper, we study those two parameters. We show that similarly to the z-number, the b-Grundy number is not monotone and can be arbitrarily smaller than the minimum of the Grundy number and the b-chromatic number. We also describe a polynomial-time algorithm that decides whether a given k-regular graph has b-Grundy number (resp. z-number) equal to $k+1$. We also prove that every cubic graph with no induced 4-cycle has b-Grundy number and z-number exactly 4.

© 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

## 1. Introduction

Graphs considered in this paper are undirected, finite and contain neither loops nor multiple edges. The definitions and notations used in this paper are standard and may be found in any textbook on graph theory. See [3] for example. We denote by $[k]$ the set $\{1, \dots, k\}$. The disjoint union of two graphs $G$ and $H$ is denoted by $G + H$. For any positive integer $k$, we denote by $kG$ the disjoint union of $k$ copies of $G$.

A k-colouring of a graph $G$ is a mapping $\phi: V \to [k]$, such that for any edge $uv \in E(G)$, $\phi(u) \neq \phi(v)$. A k-colouring may also be seen as a partition of the vertex set of $G$ into $k$ disjoint **stable sets** (i.e. sets of pairwise non-adjacent vertices) $S_i = \{v | \phi(v) = i\}$ for $1 \le i \le k$. For convenience (and with a slight abuse of terminology), by k-colouring we mean both the mapping $\phi$ or the partition $(S_1, \dots, S_k)$. The elements of $\{1, \dots, k\}$ are called **colours**, and the $S_i$, $1 \le i \le k$, are the **colour classes**. A graph is k-colourable if it has a k-colouring. The **chromatic number** $\chi(G)$ is the least $k$ such that $G$ is k-colourable.

The problem of determining the chromatic number is one of Karp's twenty one NP-hard problems [14]. It is already NP-complete to decide whether a given planar 4-regular graph admits a 3-colouring [5]. Moreover, assuming $P \neq$ NP, there is no algorithm that approximates the chromatic number within a factor of $n^{1-\epsilon}$, for all $\epsilon > 0$ [22].

To deal with this hard problem and its numerous applications, colouring heuristics have been designed. The most basic and most widespread one is the greedy algorithm. A **greedy colouring** relative to an ordering $\sigma = v_1 < v_2 < \dots < v_n$ of $V(G)$ is obtained by colouring the vertices in the order $\sigma$, assigning to $v_i$ the smallest positive integer not already used on its lowered-indexed neighbours. Denoting by $S_i$ the stable set of vertices coloured $i$, a greedy colouring has the following property:

> For every $j < i$, every vertex in $S_i$ has a neighbour in $S_j$. \hfill (★)

E-mail address: Frederic.Havet@inria.fr (F. Havet).

<footnote><sup>a</sup> Department of Computer Science, Universidade Federal do Ceará, Fortaleza, Brazil</footnote>

<footnote><sup>b</sup> CNRS, Université Côte d'Azur, 13S, INRIA, Sophia Antipolis, France</footnote>

<footnote>* Corresponding author.</footnote>
Otherwise the vertex in $S_i$ would have been coloured by an integer no greater than $j$. Conversely, a colouring satisfying Property $(\star)$ is a greedy colouring relative to any vertex ordering in which the vertices of $S_j$ precede those of $S_i$ when $j < i$. We call a vertex satisfying Property $(\star)$ a **greedy vertex**. The **Grundy number** $\Gamma(G)$ is the largest $k$ such that $G$ has a greedy $k$-colouring. It can be seen as a measure of the worst-case behaviour of the greedy algorithm.

Observe that greedy colourings may also be seen as the results of the following local improvement technique. We start with an arbitrary proper colouring. If a colour class is empty, then we suppress it. If a vertex is not a greedy vertex, then we move it into a lower-indexed stable set in which it has no neighbours. Such a move is called a **greedy improvement**.

Another heuristic is based on a different improvement technique. Given a $k$-colouring $(S_1, \dots, S_k)$, a vertex of $S_i$ is a **b-vertex** if it has a neighbour in $S_j$ for all $j \in [k] \setminus \{i\}$. The local improvement is then the following: if there is a colour class $S_i$ having no b-vertex, then we move every vertex of $S_i$ into another colour class in which it has no neighbour and remove $S_i$ (which has become empty). Such an improvement is called a **b-improvement**. A $k$-b-colouring is a $k$-colouring such that no b-improvement is possible. In other words, it is a $k$-colouring such that every colour class has a b-vertex. The **b-chromatic number** $\chi_b(G)$ is the largest $k$ such that $G$ has a $k$-b-colouring.

Instead of considering only one type of improvements, Zaker [21] considered a heuristic that performs both greedy improvements and b-improvements. Such a heuristic yields **b-greedy colourings** which are colourings that are both greedy colourings and b-colourings. The **b-Grundy number** $\Gamma_b(G)$ is the largest $k$ such that $G$ has a b-greedy $k$-colouring.

Zaker [21] showed that every b-greedy $p$-colouring can be improved (in polynomial time) into a b-greedy $q$-colouring $(S_1, \dots, S_q)$ for some $q \le p$ such that there are b-vertices $b_i$ of $S_i$, $i \in [q]$, such that $b_q$ is adjacent to all $b_j$, $j \in [q-1]$. Such a $q$-colouring is called a **q-z-colouring**. The **z-number** $z(G)$ is the largest $k$ such that $G$ has a $k$-z-colouring.

Recall that a **clique** in a graph is a set of pairwise adjacent vertices. We denote by $\omega(G)$ the **clique number** of $G$, that is the size of a largest clique in $G$.

By definition, we have

$$ \omega(G) \le \chi(G) \le z(G) \le \Gamma_b(G) \le \min\{\Gamma(G), \chi_b(G)\} \le \Delta(G) + 1 \quad (1) $$

In Section 2, we examine whether some basic properties of greedy colourings or b-colourings also hold for b-greedy colourings and z-colourings and the associated parameters $\Gamma_b(G)$ and $z(G)$.

The chromatic number (resp. Grundy number) of a graph is well-known to be equal to the maximum of the chromatic numbers (resp. Grundy numbers) of its connected components. Khaleghi and Zaker [15] (see also [8]<fnref n="1" />) recently proved the z-number of a graph is the maximum of the z-numbers of its connected components. In contrast, the b-chromatic number is greater or equal to the maximum of the b-chromatic numbers of its connected components, but it can be arbitrarily larger. For example, consider the disjoint union of $k$ stars of order $k$. Clearly, each connected component has b-chromatic number 2, but the whole graph has b-chromatic number $k$ (colour each star with $k$ different colours so that the $k$ central vertices have different colours). We show the b-Grundy number is similar to the b-chromatic number: the b-Grundy number of a graph is greater or equal to the maximum of the b-Grundy numbers of its connected components (Proposition 6), but strict inequality is possible: we describe a graph with b-Grundy number 4 which is the disjoint union of two trees of b-chromatic number 3.

We then study the z-spectrum and $\Gamma_b$-spectrum of a graph. The **z-spectrum** (resp. $\Gamma_b$-spectrum, $\Gamma$-spectrum, $\chi_b$-spectrum) of a graph $G$, denoted by $z\text{-spec}(G)$ (resp. $\Gamma_b$-spec$(G)$, $\Gamma$-spec$(G)$, $\chi_b$-spec$(G)$) is the set of values $k$ such that $G$ admits a z-colouring (resp. b-greedy colouring, Grundy colouring, b-colouring) with $k$ colours. For a parameter $\gamma$ in $\{z, \Gamma_b, \Gamma, \chi_b\}$, we say that $G$ is **$\gamma$-continuous** if $\gamma$-spec$(G) = \{\chi(G), \dots, \gamma(G)\}$. It is well-known that every graph is $\Gamma$-continuous (see e.g. [9]) while many graphs are not $\chi_b$-continuous (see e.g. [13]). We present graphs that are neither z-continuous nor $\Gamma_b$-continuous (Proposition 7). This poses the following characterization problem.

**Problem 1.** Which graphs are z-continuous? Which graphs are $\Gamma_b$-continuous?

We then study the monotonicity of $\Gamma_b$. A graph parameter $\gamma$ is said to be **monotone**, if $\gamma(G) \ge \gamma(H)$ for every induced subgraph $H$ of $G$. The Grundy number $\Gamma$ is monotone (see [1]) while the b-chromatic number $\chi_b$ is not (see e.g. [13]). Khaleghi and Zaker [15] showed that $z$ is not monotone. We show that the same holds for $\Gamma_b$ (Corollary 9).

In view of the chain of inequalities (1), it is natural to ask whether $\Gamma_b(G)$ can be bounded by a function of $z(G)$ and whether $\min\{\Gamma(G), \chi_b(G)\}$ can be bounded by a function of $\Gamma_b(G)$. Zaker [21] proved that $\min\{\Gamma(G), \chi_b(G)\}$ cannot be bounded by a function of $z(G)$: he showed that there are graphs $G$ with z-number at most 3 for which $\min\{\Gamma(G), \chi_b(G)\}$ can be arbitrarily large. In Proposition 10, we improved on Zaker's result and answer the second of the above-questions: we prove that there are graphs $G$ with b-Grundy number at most 2 (and thus z-number at most 2) for which $\min\{\Gamma(G), \chi_b(G)\}$ can be arbitrarily large. However, the first question remains open:

<footnote n="1">¹ We independently proved some results of [15]. They appeared in an earlier version of the paper [8]. Since our proofs are very similar the ones of [15] which appeared during the refereeing process of this paper, we decided to remove them.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. The four cubic graphs with b-chromatic number less than 4.</figcaption></figure>

**Problem 2.** Does there exist a function *f* such that Γ<sub>b</sub>(G) ≤ *f*(*z*(G)) for all graph *G*?

In Section 3, we study z-colourings and b-greedy colourings of trees. Khaleghi and Zaker [15] proved that trees are z-continuous. We show that trees are also Γ<sub>b</sub>-continuous, thus answering Problem 1 for trees. We then consider Problem 2 restricted to trees. Khaleghi and Zaker [15] proved that Γ(*T*) ≤ 2*z(*T*)* − 1 for every tree *T* (Theorem 15) and that the bound is tight. This implies that Γ<sub>b</sub>(*T*) ≤ 2*z(*T*)* − 1 for every tree *T*. We show that this bound is tight up to an additive constant no greater than 1 (Proposition 16).

A graph is *d*-regular if each of its vertices has degree *d*. It has been proved that a *d*-regular graph with sufficiently high order *n* has *b*-chromatic number *d* + 1 (*n* ≥ *d*<sup>4</sup> [18], *n* ≥ 2*d*<sup>3</sup> [4], *n* ≥ 2*d*<sup>3</sup> − 2*d*<sup>2</sup> + 2*d* [6]). For *cubic* (i.e. 3-regular) graphs, Jakovac and Klavžar [12] proved a more precise result: all cubic graphs have *b*-chromatic number 4 except four exceptions : the complete bipartite graph *K*<sub>3,3</sub>, the prism *K*<sub>3</sub>□*K*<sub>2</sub>, the Petersen graph *P*<sub>10</sub>, and another graph *G*<sub>10</sub> on ten vertices. See Fig. 1.

For any integer *d* ≥ 2, Gastineau et al. [7] showed an infinite family of *d*-regular graphs with Grundy number at most *d*, and made the following conjecture, which they proved for *d* = 3. (It is easy for *d* = 2.)

**Conjecture 3** (Gastineau et al. [7]). For any positive integer *d*, every *d*-regular graph with no induced 4-cycle has Grundy number *d* + 1.

As an extension of these results and conjecture, we conjecture the following.

**Conjecture 4.** For any positive integer *d*, all *d*-regular graphs with no induced 4-cycle have *z*-number *d* + 1 except a finite number of exceptions.

When *d* = 2, this conjecture holds as it is easy to see that all cycles of length at least 8 have *z*-number 3. In Section 5, we prove this conjecture for *d* = 3 by showing the following theorem.

**Theorem 5.** Let *G* be a *cubic* graph with no induced *C*<sub>4</sub>. If *G* is not the *Petersen graph*, then *z*(*G*) = 4.

In Section 4, we consider the complexity of computing the *z*-number and the *b*-Grundy number of a graph. We first prove that it is NP-hard, and more precisely that is NP-complete to decide whether a given bipartite graph *G* such that Γ(*G*) = Δ(*G*) + 1 or χ<sub>b</sub>(*G*) = Δ(*G*) + 1 satisfies *z*(*G*) = Δ(*G*) + 1 (resp. Γ<sub>b</sub>(*G*) = Δ(*G*) + 1).

In [19], it is proved that, for any parameters γ₁ in {ω, χ} and γ₂ in {Γ, χ<sub>b</sub>}, it is NP-hard to decide whether γ₁(*G*) = γ₂(*G*). We show that for any parameters γ₁ in {z, Γ<sub>b</sub>} and γ₂ in {ω, χ, Γ, χ<sub>b</sub>} it is NP-hard to decide whether γ₁(*G*) = γ₂(*G*) (Theorem 17 and Corollaries 18 and 19). We also prove the NP-hardness of deciding whether *z*(*G*) = Γ<sub>b</sub>(*G*) for a given graph *G* (Corollary 21).

In contrast, we show in Corollary 28 that one can decide in polynomial time whether a *k*-regular graph has *z*-number (resp. *b*-Grundy number) *k* + 1. Computing the Grundy number [2], the *b*-chromatic number [11] and the *z*-number [21] of a tree can be done in polynomial time. We show in Corollary 25 that deciding whether the *b*-Grundy number of a tree is at least *k* can be done in polynomial time for every fixed *k*.

Finally, in Section 6, we propose directions for further research.

**2. Properties of b-greedy colourings and z-colourings**

**Proposition 6.** Let *G* be a graph. Γ<sub>b</sub>(*G*) ≥ max {Γ<sub>b</sub>(*C*) | *C* connected component of *G*).

**Proof.** Set *m* = max {Γ<sub>b</sub>(*C*) | *C* connected component of *G*}, letting *C*<sub>1</sub>, ..., *C*<sub>*p*</sub> be the connected components of *G* such that *m* = Γ<sub>b</sub>(*C*<sub>1</sub>) ≥ Γ<sub>b</sub>(*C*<sub>2</sub>) ≥ ... ≥ Γ<sub>b</sub>(*C*<sub>*p*</sub>).

For every *i* ∈ [p] of *G*, let φ<sub>*i*</sub> be a *b*-greedy Γ<sub>b</sub>(*C*<sub>*i*</sub>)-colouring of *C*<sub>*i*</sub>. Let φ be the union of those colourings that is the colouring defined by φ(v) = φ<sub>*i*</sub>(v) for all v ∈ V(*C*<sub>*i*</sub>) and all *i* ∈ [p]. This is a greedy *m*-colouring because each φ<sub>*i*</sub> is greedy, and this is an *m*-b-colouring: all the *b*-vertices for φ<sub>*i*</sub> are also *b*-vertices for φ. Hence Γ<sub>b</sub>(*G*) ≥ *m*. □
<figure><img src="image_3.png" /><figcaption>Fig. 2. The tree $T_b$ (left) and a b-greedy 4-colouring of $2T_b$ (right).</figcaption></figure>

The inequality of Proposition 6 is not always an equality. Indeed consider the tree $T_b$ depicted on the right of Fig. 2. We have $\Gamma_b(T_b) \le \chi_b(T_b) \le 3$ because $T_b$ has only three vertices of degree 3 (and thus cannot have four b-vertices in a 4-colouring). Moreover, a b-greedy 4-colouring of $2T_b$ is shown on the left of Fig. 2. Some b-vertices, one of each colour, are indicated in grey.

Let $M_k$ be the graph obtained from the bipartite complete graph with bipartition $(X, Y)$ where $X = \{x_1, \dots, x_k\}$ and $Y = \{y_1, \dots, y_k\}$ by deleting the edges $x_iy_i$ for all $i \in [k]$.

The following proposition characterizes the z-spectrum and $\Gamma_b$-spectrum of $M_k$. It implies that $M_k$ is neither z-continuous nor $\Gamma_b$-continuous for all $k \ge 4$.

**Proposition 7.** $\text{z-spec}(M_k) = \Gamma_b\text{-spec}(M_k) = \chi_b\text{-spec}(M_k) = \{2, k\}$.

**Proof.** It is well-known that $\chi_b\text{-spec}(M_k) = \{2, k\}$. Now, as every z-colouring is a b-greedy colouring which in turn is a b-colouring, $\text{z-spec}(M_k) \subseteq \Gamma_b\text{-spec}(M_k) \subseteq \chi_b\text{-spec}(M_k) = \{2, k\}$. But the colouring $\phi_1$ that assigns colour $i$ to $x_i$ and $y_i$ for all $i \in [k]$, and the colouring $\phi_2$ that assigns 1 to all vertices in $X$ and 2 to all vertices of $Y$ are both z-colourings of $M_k$. Hence $\text{z-spec}(M_k) = \Gamma_b\text{-spec}(M_k) = \chi_b\text{-spec}(M_k) = \{2, k\}$. $\square$

Let $N_k$ be the graph obtained from $M_{k-1}$ by adding the edge $x_{k-1}y_{k-1}$.

**Proposition 8.** $z(N_k) = \chi_b(N_k) = 2$ for every integer $k \ge 2$.

**Proof.** Consider a b-colouring $\phi$ of $N_k$. Every vertex of $X \setminus \{x_{k-1}\}$ is adjacent to no vertex of colour $\phi(x_{k-1})$. Therefore, in $X$, there can only be b-vertices coloured $\phi(x_{k-1})$. Similarly, in $Y$, there can only be b-vertices coloured $\phi(y_{k-1})$. Hence, there can only be b-vertices of two different colours. So $\phi$ is a 2-colouring. $\square$

**Corollary 9.** z and $\Gamma_b$ are not monotone.

**Proof.** $z(N_{k+2}) = \chi_b(N_{k+2}) = 2$ by Proposition 8. But $N_{k+2}$ contains $M_k$ and $z(M_k) = \chi_b(M_k) = k$ by Proposition 7. $\square$

Let $S_k$ be the star on $k$ vertices. It is well-known and easy to check that $\Gamma(N_k) = k$, $\Gamma(kS_k) = 2$, and $\chi_b(kS_k) = k$.

**Proposition 10.** For every $k$, there is a graph $G_k$ such that $z(G_k) = \Gamma_b(G_k) = 2$ and $\min\{\Gamma(G_k), \chi_b(G_k)\} = k$.

**Proof.** Let $G_k = N_k + kS_k$. We have $\Gamma(G_k) \ge \Gamma(N_k) = k$ and $\chi_b(G_k) \ge \chi_b(kS_k) = k$. Therefore, since $\Delta(G_k) = k-1$, we have $\Gamma(G_k) = \chi_b(G_k) = k$.

Suppose now for a contradiction that $G_k$ admits a b-greedy $p$-colouring $\phi$ with $p \ge 3$. The restriction of this colouring to $kS_k$ is a greedy colouring. Hence, because $\Gamma(kS_k) = 2$, only colour 1 and 2 appear on $kS_k$. In particular, there is no b-vertex in $kS_k$, so all the b-vertices are in $N_k$. Hence the restriction of $\phi$ to $N_k$ is a $p$-b-colouring. This contradicts the fact that $\chi_b(N_k) = 2$ by Proposition 8. $\square$

Let us now establish an upper bound for the z-number of a graph $G$. Let $m_z(G)$ be the largest integer $i$ such that there is a vertex $v \in V(G)$ having (at least) $i$ neighbours with degree at least $i$.

**Lemma 11.** $z(G) \le m_z(G) + 1$.

**Proof.** Let $c$ be a $k$-z-colouring. There is a vertex $v_k$ with $c(v) = k$ which is also adjacent to $v_1, v_2, \dots, v_{k-1}$ where $v_i$ is a b-vertex of colour $i$ and therefore $d(v_i) \ge k-1$, for every $i \in [k-1]$. Thus, $m_z(G) \ge k-1$. In particular, if $k = z(G)$, we have $z(G) \le m_z(G) + 1$. $\square$
<figure><img src="image_4.png" /><figcaption>Fig. 3. The k-binomial trees for $k \in [4]$. The black vertices are their roots.</figcaption></figure>

### 3. Trees

**Lemma 12.** Let $T$ be a tree and $T'$ be a subtree of $T$ and $k \ge 2$ an integer. Every $k$-z-colouring (resp. b-greedy $k$-colouring) of $T'$ can be extended into a $k$-z-colouring (resp. b-greedy $k$-colouring) of $T$.

*Proof.* Let $\phi$ be a $k$-colouring of $T'$. We can extend it to $T$ as follows. For each connected component $C$ of $T - T'$, let $r$ and $s$ be the vertices of $C$ and $T'$ respectively which are adjacent. Colour the vertices of $C$ with colour 1 and 2 so that $r$ gets a colour different from $\phi(s)$.

One easily sees that if $\phi$ was a $k$-z-colouring (resp. b-greedy $k$-colouring) of $T'$, then the resulting colouring is a $k$-z-colouring (resp. b-greedy $k$-colouring) of $T$. $\square$

Khaleghi and Zaker [15] proved that trees are z-continuous. It can be easily derived from the above lemma. We now show that trees are also $\Gamma_b$-continuous.

**Theorem 13.** Every tree is $\Gamma_b$-continuous.

*Proof.* Let $T$ be a tree. Set $p = \Gamma_b(T)$, and let $\phi$ be a b-greedy $p$-colouring of $T$ with b-vertices $b_1, \dots, b_p$.

Let $2 \le q < p$. Let $F'$ be the subgraph of $T$ induced by the vertices with colours in $[q]$. One easily checks that $\phi$ is a b-greedy $q$-colouring of $F'$ with b-vertices $b_1, \dots, b_q$. We now try to extend greedily this colouring into a $q$-colouring of $T$ as follows: as long as there is an uncoloured vertex $v$ of $T$ which is adjacent to at least one already coloured vertex, we colour $v$ with the smallest integer in $[q]$ not assigned to a neighbour of $v$ if such an integer exists, and we stop if there is no such integer.

If this procedure manages to colour all vertices, then the resulting colouring is a b-greedy colouring of $T$ (with b-vertices $b_1, \dots, b_q$). Otherwise, the procedure stopped at some vertex $v$ which has $q$ neighbours $w_1, \dots, w_q$ with $w_i$ coloured $i$.

For all $i \in [q]$, let $C_i$ be the connected component containing $w_i$ in the subgraph $F$ of $T$ induced by the already coloured vertices. By the way we extended the colouring, each $C_i$ contains at least one vertex in $\{b_1, \dots, b_q\}$ and thus exactly one. Now consider $w_q$. Since we extended a greedy (partial) colouring greedily, $w_q$ has a neighbour of each colour in $[q-1]$, so $w_q$ is a b-vertex of colour $q$. Let $i_q$ be the index such that $b_q \in C_{i_q}$. Uncolour the vertices of $C_{i_q}$ and colour $v$ with $i_q$. Then the subgraph induced by the set of coloured vertices $(V(F) \setminus V(C_{i_q})) \cup \{v\}$ is a tree $T'$ and the colouring is a b-greedy colouring of $T'$ with b-vertices $b_1, \dots, b_{q-1}, w_q$ (if $i_q \neq q$), and with b-vertices $b_1, \dots, b_{q-1}, v$ if $i_q = q$. Thus, by Lemma 12, $T$ admits a b-greedy $q$-colouring. $\square$

The **binomial trees** $B_k$, $k \in \mathbb{N}$, are defined inductively as follows. The 1-binomial tree $B_1$ is the graph with one vertex and no edges; its root is its vertex. For every $k > 1$, k-binomial $B_k$ is obtained from the disjoint union of $B_1, \dots, B_{k-1}$ by adding a new vertex $r$ linked to the roots of those trees; the new vertex $r$ is the root of $B_k$. See Fig. 3 for some examples. Note that $|V(B_k)| = 2^{k-1}$.

Binomial trees play an important role in greedy colouring of trees as shown by Beyer et al. [2].

**Lemma 14** (Beyer et al. [2]). A tree has Grundy number at least $k$ if and only if it contains the $k$-binomial tree $B_k$ as a subtree.

**Theorem 15** (Khaleghi and Zaker [15]). If $T$ is a tree, then $\Gamma(T) \le 2z(T) - 1$ and equality holds for binomial trees.

Because $\Gamma_b(T) \le \Gamma(T)$, this implies that $\Gamma_b(T) \le 2z(T) - 1$.

This is tight up to a small additive constant as shown by the following proposition.

**Proposition 16.** For every $k \ge 4$, there is a tree $T_k$ such that $\Gamma_b(T_k) = k$ and $z(T_k) \in \{\lceil k/2 \rceil + 1, \lceil k/2 \rceil + 2\}$.
<figure><img src="image_5.png" /><figcaption>Fig. 4. Representation of $F_k^i$ and $T_k$. The black vertices represent the leaves of $F_k^i$ and $F_k^{i+1}$ that are identified, for $i \in [k-3]$.</figcaption></figure>

**Proof.** Given a copy of $B_k$ and an integer $i \in [k]$, let $v_i$ be the neighbour of the root of $B_k$ that has degree $i$ and let $B_k^{-i}$ be the tree obtained from $B_k$ by removing $v_i$ and the vertices of the $B_i$ rooted on $v_i$. For $i \in [k-2]$ we define $F_k^i$ as the tree constructed as follows: for $j \in [i-1]$, $\ell \in \{i+1, \dots, k\}$, we add the vertex $r_i$ and a copy of $B_j$ with root $v_j^i$ and a copy of $B_\ell^{-i}$ with root $v_\ell^i$ along with the edges $r_i v_j^i$, $r_i v_\ell^i$.

Now we are ready to construct $T_k$. We start by adding a copy of $F_k^i$, for every $i \in [k-2]$. Then, for $j \in [k-3]$, we connect $F_k^j$ with $F_k^{j+1}$ by identifying the leaf (vertex of degree 1) adjacent to $r_{j+1}$ with the leaf of $F_k^j$ that is the most distant from $r_j$ (at distance $k-1$). See Fig. 4.

**Claim 16.1.** $\Gamma_b(T_k) = k$.

**Proof.** Note that $\Delta(T_k) = k-1$ so $\Gamma_b(T_k) \le k$. We now construct a b-greedy colouring $c$ of $T_k$ with exactly $k$ colours. For each $i \in [k-2]$, we can greedily colour $F_k^i$ in the following way: for $j < i$, we greedily colour the $B_j$ rooted in $v_j^i$ so that $c(v_j^i) = j$. Then, by setting $c(r_i) = i$, the coloured vertices induce a $B_i$ rooted in $r_i$ and we denote it by $B$. Now, for $i < \ell \le k$, the $B_\ell^{-\ell}$ rooted in $v_\ell^i$ plus the vertices of $B$ induces a $B_\ell$ and we can greedily extend the colouring so that $c(v_\ell^i) = \ell$.

Observe that on a $k$-colouring of a $B_k$, all vertices of degree 1 have colour 1. Therefore, since, for all $j \in [k-3]$, the vertex $v = V(F_k^j) \cap V(F_k^{j+1})$ is a leaf in both $F_k^i$ and $F_k^{j+1}$, it will receive colour 1 if these graphs are coloured independently as described above. Furthermore, for every $i \in [k-2]$, the vertex $r_i$ is a b-vertex of colour $i$, and $v_{k-1}^i$, $v_k^i$ are also b-vertices because $c$ is greedy. Thus, $c$ is a b-greedy $k$-colouring.

**Claim 16.2.** $z(T_k) \in \{\lceil k/2 \rceil + 1, \lfloor k/2 \rfloor + 2\}$.

**Proof.** We shall first prove that $m_z(T_k) \le \lfloor k/2 \rfloor + 1$, which by Lemma 11, implies $z(T_k) \le \lfloor k/2 \rfloor + 2$.

Assume for a contradiction that $m_z(T_k) \ge \lfloor k/2 \rfloor + 2$. Then there is a vertex $v \in V(T_k)$ with $\lfloor k/2 \rfloor + 2$ neighbours, all with degree at least $\lfloor k/2 \rfloor + 2$. For $i \in [k-2]$, $r_i$ has exactly one neighbour of degree $j$, for $j \in [k-1]$, so at most $\lceil (k-1)/2 \rceil - 1 = \lfloor k/2 \rfloor - 1$ neighbours with degree at least $\lfloor k/2 \rfloor + 2$ and therefore $v \ne r_i$. Similarly, $v \ne v_j^i$ for $j \in [k-1] \setminus \{i\}$, because $v_j^i$ has $\lfloor j/2 \rfloor + 1$ neighbours with degree at least $\lfloor j/2 \rfloor + 2$ if $j < i$ and only $\lfloor j/2 \rfloor$ such neighbours if $j > i$. Finally, any other vertex $w$ and its neighbours are all contained in a $k$-binomial tree and $m_z(B_k) = \lfloor k/2 \rfloor$ so $v \ne w$. This is a contradiction.

Set $p = \lceil k/2 \rceil + 1$. Let us describe a $z$-colouring $c$ with $p$ colours. We give to the vertex $v_k^1$ the colour $p$ and we set $c(r_1) = 1$. Now let $w_1 = r_1$ and let $w_2, w_3, \dots, w_{p-1}$ be the neighbours of $v_k^1$ with the respective degrees $k-1, k-2, \dots, k-(p-2)$ that were not coloured yet. We give the $p-2$ remaining colours $2, 3, \dots, p-1$ to the vertices $w_2, w_3, \dots, w_{p-1}$ in this order. As $w_i$ is a root of a subtree $W_i$ that contains $B_{p-1}$, we can greedily colour $W_i$ in such a way that $w_i$ becomes a b-vertex of colour $i$. To conclude, we colour the other vertices of $T_k$ using the colours 1 and 2, which is possible because $T_k$ is bipartite. As $v_k^1$ is neighbour of a b-vertex of colour $i$ for every $i \in [p-1]$, we have that $c$ is a $z$-colouring. $\square$

# 4. Complexity

## 4.1. NP hardness

Havet and Sampaio [10] showed that deciding whether $\Gamma(G) = \Delta(G) + 1$ for a given graph $G$ is NP-complete even if $G$ is bipartite. Khaleghi and Zaker [15] adapt their proof to show that the same holds for $z$. Note that their proof also works for $\Gamma_b$ (See also [8]). We thus have the following.

**Theorem 17.** It is NP-complete to decide whether a given bipartite graph $G$ such that $\Gamma(G) = \Delta(G) + 1$ satisfies $\Gamma_b(G) = \Delta(G) + 1$.
<figure><img src="image_6.png" /><figcaption>**Fig. 5.** The graph $L_5$.</figcaption></figure>

**Corollary 18.** It is NP-complete to decide whether a given bipartite graph $G$ (such that $\chi_b(G) = \Delta(G) + 1$) satisfies $\Gamma_b(G) = \chi_b(G)$ (resp. $z(G) = \chi_b(G)$).

**Proof.** Let $G$ be a bipartite graph. Set $k = \Delta(G) + 1$.

Let $G' = G + kS_k$. We clearly have $\chi_b(G) = k = \Delta(G') + 1$ because $\chi_b(kS_k) = k$. Now as in **Proposition 10**, in every $b$-greedy colouring of $G'$ the vertices of $kS_k$ are coloured 1 or 2. Hence $G'$ has a $b$-greedy $k$-colouring (resp. $k$-z-colouring) if and only if $G$ does.

**Theorem 17** yields the result. $\square$

Zaker [20] showed that deciding whether $\chi(G) = \Gamma(G)$ is co-NP-complete. Later, Khaleghi and Zaker [15] showed that deciding $\chi(G) = z(G)$ and deciding $\omega(G) = z(G)$ are also co-NP-complete. We can deduce analogous results for several pairs of parameters.

**Corollary 19.** Given a graph $G$ and two parameters $\gamma_1 \in \{\omega, \chi\}$ and $\gamma_2 \in \{z, \Gamma_b\}$, the problem of deciding whether $\gamma_1(G) = \gamma_2(G)$ is NP-hard.

**Proof.** We give a reduction from the problem of deciding whether a given bipartite graph $G'$ satisfies $\gamma_2(G') = \Delta(G') + 1$ which is NP-complete by **Theorem 17**.

Let $G'$ be an instance of this problem and let $G = G' + K_{\Delta(G')}$. We claim that $\gamma_2(G) \neq \gamma_1(G)$ if and only if $\gamma_2(G') = \Delta(G') + 1$.

Since $G'$ is bipartite, $\omega(G') \le \chi(G') \le 2$, that is $\gamma_1(G') \le 2$. Hence $\gamma_1(G) = \gamma_1(K_{\Delta(G')}) = \Delta(G')$. In addition, by **Proposition 6** $\gamma_2(G) \ge \Gamma_b(G) \ge \Gamma_b(K_{\Delta(G')}) = \Delta(G')$.

Assume that there is a $b$-greedy colouring $\phi$ of $G$. Then all the $b$-vertices are in $G'$ because $\Delta(K_{\Delta(G')}) < \Delta(G')$. Now the restriction of $\phi$ to $G'$ is a greedy colouring (because it is the restriction of a greedy colouring to one of its connected components) and a $(\Delta(G') + 1)$-b-colouring, and thus a $b$-greedy $(\Delta(G') + 1)$-colouring. Consequently, $\gamma_2(G) = \Delta(G) + 1$ if and only if $\gamma_2(G') = \Delta(G') + 1$. Thus, $\gamma_2(G) \ne \gamma_1(G) = \Delta(G')$ if and only if $\gamma_2(G') = \Delta(G') + 1$. $\square$

**Remark 20.** Corollary 19 implies that deciding whether $\chi(G) = \Gamma_b(G)$ is co-NP-complete. Indeed a proper colouring with $\gamma$ colours and a $b$-greedy colouring with $\gamma'$ colours such that $\gamma' > \gamma$ form a certificate that $\chi(G) < \Gamma_b(G)$ (resp. $\chi(G) < z(G)$).

**Corollary 21.** Is NP-hard to decide whether $z(G) = \Gamma_b(G)$.

**Proof.** Let $D_d$ be the disjoint union of a complete graph $K_d^1$ with vertex set $\{v_1^1, \dots, v_d^1\}$ and three complete graphs $K_{d-1}^j$, $i \in \{2, 3, 4\}$ with vertex set $\{v_1^i, \dots, v_{d-1}^i\}$. Let $L_d$ be the graph obtained from $D_d$ by removing the edge $v_1^1v_2^1$ and adding a new vertex $v_0$ along with the edges $v_0v_1^2, v_{d-1}^2v_1^3, v_{d-1}^3v_{d-1}^4$. See **Fig. 5** for an example.

**Claim 21.1.** $\Gamma_b(L_d) = d$ and $z(L_d) \le d - 1$.

**Proof.** Since $\Delta(L_d) = d - 1$, we have $z(L_d) \le \Gamma_b(L_d) \le d$.

Consider the following proper colouring $\phi$ of $L_d$: $\phi(v_0) = 1$, $\phi(v_1^1) = i$, for $i \in [d]$ and, for $i \in [d-1], j \in \{2, 3, 4\}$, $\phi(v_i^j) = \begin{cases} d, & \text{if } i = d - 1 \text{ and } j = 3 \\ i, & \text{otherwise.} \end{cases}$

On easily checks that $\phi$ is a $b$-greedy colouring of $L_d$ with b-vertices $v_1^3$ and $v_1^1$, $i \in \{2, 3, \dots, d\}$, so $\Gamma_b(L_d) \ge d$.

One easily checks that $m_z(L_d) = d - 2$, so, by **Lemma 11**, $z(L_d) \le d - 1$.

We now give a reduction from the problem of deciding whether $z(G) = \Delta(G) + 1$ for a given graph $G$, which is NP-complete by **Theorem 17**. Let $G$ be the graph and let $G'$ be the disjoint union of $G$ and $L_{\Delta(G)+1}$. Since $\Delta(G') = \Delta(G)$, we have that $\Gamma_b(G') \le \Delta(G)+1$. By **Claim 21.1** and **Proposition 6**, we have $\Gamma_b(G') \ge \Delta(G)+1$ and therefore $\Gamma_b(G') = \Delta(G)+1$. By **Claim 21.1**, $z(L_{\Delta(G)+1}) \le \Delta(G)$. Thus $z(G') = \Delta(G) + 1 = \Gamma_b(G')$, if and only if $z(G) = \Delta(G) + 1$. $\square$
## 4.2. Atoms and polynomial-time algorithms

Zaker [20] showed that for every positive integer $j$ there exists a finite set $A_j^\Gamma$ of graphs, called **greedy j-atoms**, such that for any graph $G$ the following holds: $\Gamma(G) \ge j$ if and only if $G$ contains a $j$-greedy atom as an induced subgraph. Moreover, he showed that every element of $A_j^\Gamma$ has at most $2^{k-1}$ vertices. The following lemma follows directly from this fact and is implicitly used in many papers.

**Lemma 22.** Let $G$ be a graph, $\phi$ a greedy colouring of $G$, and $v$ a vertex of $G$. Then $G$ contains an induced subgraph $H$ containing $v$ which is a $\phi(v)$-greedy atom and such that $\phi$ is a greedy $\phi(v)$-colouring of $H$.

The following is also implicit in Section 3 of Zaker [21].

**Lemma 23.** Let $G$ be a graph. If $\phi$ is a $k$-z-colouring of $G$, then there is an induced subgraph $H$ of order at most $(k-3)2^{k-1}+k+2$ such that $\phi$ is a $k$-z-colouring of $H$.

We now prove the analogue for b-greedy colouring.

**Lemma 24.** Let $G$ be a graph. If $\phi$ is a $b$-greedy $k$-colouring of $G$, then there is an induced subgraph $H$ of order at most $(k-1)2^k + k + 1$ such that $\phi$ is a $b$-greedy $k$-colouring of $H$.

**Proof.** Let $\phi$ be a $b$-greedy colouring of $G$. For $i \in [k]$, let $b_i$ be a $b$-vertex of $G$ coloured $i$. For each $i \in [k]$, and $j \in [k] \setminus \{i\}$, let $c_i^j$ be the neighbour of $b_i$ coloured $j$. By Lemma 22, there is an induced subgraph $H_i^j$ containing $c_i^j$ which is a $j$-greedy-atom and such that $\phi$ is a $j$-greedy colouring of $H_i^j$. Let $H$ be the subgraph of $G$ induced by $\bigcup_{i \in [k]} (\{b_i\} \cup \bigcup_{j \in [k] \setminus \{i\}} V(H_i^j))$. Clearly, $\phi$ is a greedy colouring of $H$ in which each $b_i$ is a $b$-vertex. Therefore $\phi$ is a $b$-greedy colouring of $H$. Now every $j$-greedy atom has size at most $2^{j-1}$, thus $|\bigcup_{j \in [k] \setminus \{i\}} V(H_i^j)| \le 2^k - 2^{i-1}$. Hence $|H| \le (k-1)2^k + k + 1$. $\square$

A **k-z-atom** is a graph $G$ having a $k$-z-colouring $\phi$ that is not a $k$-z-colouring of any strict induced subgraph $H$ of $G$. Similarly, a **b-greedy k-atom** is a graph $G$ having a b-greedy $k$-colouring $\phi$ that is not a b-greedy $k$-colouring of any strict induced subgraph $H$ of $G$. Notice that with those definitions of $k$-z-atom and b-greedy $k$-atom, it is not known whether generating the $k$-z-atoms or the b-greedy $k$-atoms can be done in polynomial time for fixed $k$. Zaker [21] gave a different notion of z-atom which allows the generation of z-atoms in polynomial time.

Lemmas 23 and 24 imply that, for any fixed $k$, the number of $k$-z-atoms and the number of b-greedy $k$-atoms is finite. By definition, a graph with z-number $k$ (resp. b-Grundy number $k$) contains a $k$-z-atoms (resp. b-greedy $k$-atom). But, in contrast to the Grundy number, the converse is not true because the $k$-z-colouring (resp. b-greedy $k$-colouring) of an induced subgraph cannot always be extended into a $k$-z-colouring (resp. b-greedy $k$-colouring) of the whole graph. Nevertheless, the converse is true for some graph classes. This is in particular the case for trees as shown by Lemma 12. This directly implies that, for any fixed $k$, deciding whether a given tree $T$ has b-Grundy number (resp. z-number) at least $k$ can be done in polynomial time.

**Corollary 25.** For any fixed $k$, deciding whether a given tree $T$ has b-Grundy number at least $k$ can be done in polynomial time.

A similar approach using atoms allows to decide in polynomial-time whether the z-number (resp. b-Grundy number) of a $k$-regular graph is $k+1$.

**Lemma 26.** Let $G$ be a $k$-regular graph. If $G$ has an induced subgraph $H$ such that $z(H) = k+1$ (resp. $\Gamma_b(H) = k+1$), then $z(G) = k+1$ (resp. $\Gamma_b(G) = k+1$).

**Proof.** Since $G$ is $k$-regular, then every greedy $(k+1)$-colouring $\phi$ of a subgraph $H$ can be greedily extended into a greedy $(k+1)$-colouring $\psi$ of $G$. Moreover, if $\phi$ was a z-colouring (resp, a b-greedy colouring), then $\psi$ is also a z-colouring (resp. a b-greedy colouring), because the b-vertices for $\phi$ remain b-vertices for $\psi$. $\square$

**Corollary 27.** Let $G$ be a $k$-regular graph.

(i) $z(G) = k+1$ if and only if $G$ contains a $(k+1)$-z-atom.

(ii) $\Gamma_b(G) = k+1$ if and only if $G$ contains a b-greedy $(k+1)$-atom.

**Corollary 28.** Let $k$ be a fixed integer. Deciding whether the z-number (resp. b-Grundy number) of a given $k$-regular graph is $k+1$ is polynomial-time solvable.

**Proof.** Given a $k$-regular graph, deciding whether $z(G) = k+1$ is equivalent to decide whether $G$ has a $(k+1)$-z-atom by Corollary 27. But, by Lemma 23, there is a finite number of $(k+1)$-z-atoms, all of size at most $a_k = (k-2)2^k + k + 3$. Hence one can check in time $O(|V(G)|^{ak})$ whether $G$ contains a $(k+1)$-z-atom.

The proof for the b-Grundy number is similar using Lemma 24 in place of Lemma 23. $\square$
<figure><img src="image_7.png" /><figcaption>Fig. 6. The graphs $I_1, I_2$, and $I_3$ made of two intersecting 6-cycles.</figcaption></figure>

**5. Cubic graphs**

The aim of this section is to prove **Theorem 5**, which states that every cubic graph with no induced $C_4$ other than the Petersen graph has z-number and b-Grundy number equal to 4.

To prove **Theorem 5**, we divide the proof into three cases. The first one considers cubic graphs of girth at least 6 (**Theorem 31**), the second one cubic graphs of girth exactly 5 (**Theorem 32**), and the third one cubic graphs of girth 3 (**Theorem 33**).

We need the following lemmas.

**Lemma 29.** Let $F$ be an acyclic graph whose vertex set is the union of three stable sets $X, Y, Z$ of size 2 such that every vertex is adjacent to at most one vertex in each of those three sets. Then there is a stable set with one vertex in each of $X, Y, Z$.

**Proof.** Set $X = \{x_1, x_2\}$, $Y = \{y_1, y_2\}$, and $Z = \{z_1, z_2\}$. The results holds trivially if $F$ has no edge, so we may assume that $F$ has at least one edge.

Assume $F$ contains a path of length 2, say $x_1y_1z_1$. Since $T$ is acyclic, $x_1$ is not adjacent to $z_1$, and since every vertex is adjacent to at most one vertex in $Y$, $x_1$ and $z_1$ are not adjacent to $y_2$. Hence $\{x_1, y_2, z_1\}$ is the desired stable set. Henceforth, we may assume that $F$ contains no path of length 2.

$F$ has an edge, say $x_1y_1$. Then $x_1$ is not adjacent to $y_2$, $z_1$ and $z_2$. But $y_2$ is not adjacent to a vertex of $Z$, say $z_1$. Then $\{x_1, y_2, z_1\}$ is the desired stable set. $\square$

**Lemma 30.** Let $G$ be a cubic graph of girth at least 5, and $x$ and $y$ be two vertices of $G$. There are two vertices distinct from $y$ which are adjacent to $x$ and non-adjacent to $y$.

**Proof.** If $x$ is adjacent to $y$. Let $w_1$ and $w_2$ be the neighbours of $x$ distinct from $y$. They are non-adjacent to $y$ for otherwise, there would be a 3-cycle, so they are the desired vertices.

If $x$ and $y$ are non-adjacent, then $x$ and $y$ have at most one vertex in common, for otherwise there is a 4-cycle. Hence at least two neighbours of $x$ are non-adjacent to $y$. $\square$

**Theorem 31.** If $G$ is a cubic graph of girth at least 6, then $z(G) = \Gamma_b(G) = 4$.

**Proof.** Let $G$ be a cubic graph. We have $z(G) \le \Gamma_b(G) \le 4$.

Assume that $G$ has girth at least 6. We shall prove that $z(G) \ge 4$. To do so, thanks to **Lemma 26**, it suffices to exhibit an induced subgraph of $G$ and 4-z-colouring of it. That is what we will do.

We distinguish five cases depending on the existence of 6-cycles and how they intersect.

*Case 1:* Assume first that $G$ contains the graph $I_1$ depicted in Fig. 6 as a (necessarily induced) subgraph.

For $i \in [3]$, let $c'_i$ be the neighbour of $b_i$ not in $V(I_1)$, and let $d_i$ be the neighbour of $c_i$ not in $V(I_1)$.

Suppose first that $d_1$ has a neighbour $e_1$ distinct from $c_1$ which is non-adjacent to both $c'_2$ and $c'_3$. Note that among the above-mentioned vertices $e_1$ can only be adjacent to $b_3$ and $b_2$. Therefore the subgraph induced by $\tilde{V}(I_1) \cup \{c'_1, c'_2, c'_3, d_1, e_1\}$ is the configuration $J_1$ depicted in Fig. 7. Set $\phi(a) = 4$, $\phi(b_3) = \phi(c_1) = \phi(c_2) = 3$, $\phi(b_2) = \phi(c'_1) = \phi(c_3) = \phi(d_1) = 2$, $\phi(b_1) = \phi(c'_2) = \phi(c'_3) = \phi(d) = \phi(e_1) = 1$. See Fig. 7. Observe that for each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of $J_1$.

Henceforth we may assume that the two neighbours of $d_1$ distinct from $c_1$ are adjacent to either $c'_2$ or $c'_3$. Since there is no 4-cycle, then one of them, say $d'_2$, is adjacent to $c'_2$ and the other, say $d'_3$, is adjacent to $c'_3$. By symmetry, interchanging the role of $d_1$ and $d_3$, we get that $d_3$ has a neighbour $d'_1$ adjacent to $c'_1$ and not $c'_2$. Applying the same reasoning interchanging the role of $d, c_1, c_2, c_3$ with $a, b_3, b_2, b_1$ respectively, either we find a 4-z-colouring of $G$, or $d_2$ and $c'_2$ have a common neighbour, say $e_2$. Now since $G$ has girth 6, the vertices $d_2, d'_2, c'_1$ and $d'_3$ are distinct. Hence since $G$ is cubic, the vertex $d'_1$ is non-adjacent to at least one vertex in $\{d_2, d'_2\}$.
<figure><img src="image_8.png" /><figcaption>Fig. 7. The configuration $J_1$ and its 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 8. The configurations $J'_1$ and $J''_1$ and their partial 4-z-colourings. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

If $d'_1$ is non-adjacent to $d'_2$, then we are in the configuration $J'_1$ depicted in Fig. 8. Set $\phi(a) = 4$, $\phi(b_2) = \phi(c'_1) = \phi(c_3) = 3$, $\phi(b_1) = \phi(c'_2) = \phi(c'_3) = \phi(d) = 2$, $\phi(b_3) = \phi(c_1) = \phi(c_2) = \phi(d'_1) = \phi(d'_2) = 1$. Observe that for each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of an induced subgraph of G.

If $d'_1$ is non-adjacent to $d_2$, then we are in the configuration $J''_1$ depicted in Fig. 8. Set $\phi(a) = 4$, $\phi(b_1) = \phi(c_2) = \phi(c_3) = 3$, $\phi(b_2) = \phi(c'_1) = \phi(c'_2) = \phi(d) = 2$, and $\phi(b_3) = \phi(c_1) = \phi(c'_2) = \phi(d_2) = \phi(d'_1) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of an induced subgraph of G.

This completes the proof of Case 1.

**Case 2:** Assume that G contains the graph $I_2$ depicted in Fig. 6 as a (necessarily induced) subgraph.

For $i \in [3]$, let $c'_1$ be the neighbour of $b_1$ not in $V(I_2)$. By Lemma 30, $c'_1$ has two neighbours which are not adjacent to $d_3$, so there is a vertex $d'_1$ distinct from $b_1$ which is adjacent to $c'_1$ and not adjacent to $d_3$.

For $i \in [3]$, let $c'_1$ be the neighbour of $b_1$ not in $V(I_2)$. By Lemma 30, $c'_1$ has two neighbours which are not adjacent to $d_3$, so there is a vertex $d'_1$ distinct from $b_1$ which is adjacent to $c'_2$ and not adjacent to $d_3$. We may assume that $d_1$ is not adjacent to $c'_2$ and $d_3$ is not adjacent to $c'_1$ for otherwise G contains $I_1$ and we are in Case 1. Hence, the subgraph induced by $V(I_2) \cup \{c'_1, c'_2, c'_3, d'_1\}$ is a configuration $J_2$ depicted in Fig. 9. Set $\phi(a) = 4$, $\phi(b_1) = \phi(c_2) = \phi(c_3) = 3$, $\phi(b_3) = \phi(c'_1) = \phi(c'_2) = \phi(d_1) = 2$, $\phi(b_2) = \phi(c_1) = \phi(c'_2) = \phi(d'_1) = \phi(d_3) = 1$. Observe that for each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of $J_2$.

This completes the proof of Case 2.

**Case 3:** Assume that G contains the graph $I_3$ depicted in Fig. 6 as a subgraph. We may assume that $c_1d_3$ and $c_3d_1$ are not edges for otherwise G contains $I_1$ and we are in Case 1. Let $c'_1$ be the neighbour of $b_1$ distinct from a and $c_1$, and $c'_2$ be the neighbour of $b_3$ distinct from a and $c_3$. The subgraph induced by $V(I_3) \cup \{c'_1, c'_3\}$ is a configuration $J_3$ as depicted on Fig. 10. Set $\phi(a) = 4$, $\phi(b_3) = \phi(c_1) = \phi(c'_2) = 3$, $\phi(b_2) = \phi(c'_1) = \phi(c_3) = \phi(d_1) = 2$, $\phi(b_1) = \phi(c_2) = \phi(c'_2) = \phi(d_3) = 1$. Observe that for each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of $J_3$.

This completes the proof of Case 3.

**Case 4:** G contains a 6-cycle that intersects no other 6-cycle. Let $C = (a, b_1, c_1, d, c_2, b_2, a)$ be a 6-cycle that intersects no other 6-cycles. Let $b_3$ be the neighbour of a not in $V(C)$. Let $c'_1$ (resp. $c'_2$) be the neighbour of $b_1$ (resp. $b_2$) not in
<figure><img src="image_10.png" /><figcaption>Fig. 9. The configuration $J_2$ and its 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 10. The configuration $J_3$ and its 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 11. The configuration $J_4$ and its 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

V(C), and let $c_3$ and $c'_3$ be the two neighbours of $b_3$ distinct from a. Let $d'_2$ be a neighbour of $c'_2$ distinct from $b_2$. By Lemma 30, $c'_3$ has a neighbour $d'_3$ distinct from $b_3$ which is not adjacent to $d'_2$. Observe that $d'_2$ and $c_3$ are not adjacent for otherwise $(a, b_2, c'_2, d'_2, c_3, b_3, a)$ would be a 6-cycle intersecting C (and we would be in Case 3). Similarly, d and $c'_3$ are not adjacent for otherwise $(a, b_2, c_2, d, c'_2, b_3, a)$ would be a 6-cycle intersecting C (and we would be in Case 1). Therefore the subgraph induced by $V(C) \cup \{b_3, c'_1, c'_2, c_3, c'_3, d'_2, d'_3\}$ is the configuration $J_4$ depicted on Fig. 11. Set $\phi(a) = 4$, $\phi(b_3) = \phi(c_1) = \phi(c'_2) = 3$, $\phi(b_2) = \phi(c'_1) = \phi(c'_3) = \phi(d) = 2$, $\phi(b_1) = \phi(c_2) = \phi(c_3) = \phi(d'_2) = \phi(d'_3) = 1$. Observe that for each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 5. Hence $\phi$ is a 4-z-colouring of $J_4$.

This completes Case 4.

Case 5: G has girth at least 7.

Let $b_4$ be a vertex of G, and let $b_1, b_2, b_3$ be its three neighbours. Let $c_2, c_3$ the neighbours of $b_1$ distinct from $b_4$, $c_1, c'_3$ be the neighbours of $b_2$ distinct from $b_4$, and $c'_1, c'_2$ be the neighbours of $b_3$ distinct from $b_4$. As highlighted on the top of Fig. 12, the subgraph T induced by those ten vertices is a tree for otherwise there would be a cycle of length at most 5. Observe that no vertex of $G-T$ is adjacent to more than one vertex of T for otherwise, there would be a cycle of length at most 6.
<figure><img src="image_13.png" /><figcaption>Fig. 12. The configurations $J_5$ and $J_6$. Dotted lines represent non-edges. The vertices inside the grey rectangle induce a tree $T$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 13. The graphs $I_5$ and $I_6$ made of two intersecting 5-cycles.</figcaption></figure>

Let $d_2$ be a neighbour of $c_3$ distinct from $b_1$. Assume that $d_2$ has a neighbour $d_1$ adjacent to a vertex in $\{c_1, c'_1, c'_2, c'_3\}$. By symmetry we may assume, that $d_1$ is adjacent to $c'_3$. Among the two neighbours of $c'_2$ distinct from $b_3$, at least one of them, say $d'_1$ is not adjacent to $d_1$ for otherwise there would be a 4-cycle. Then the subgraph induced by $\{b_1, b_2, b_3, b_4, c_1, c_2, c_3, c'_1, c'_2, c'_3, d_1, d_2, d'_1\}$ is the configuration $J_5$ depicted in Fig. 12. Assigning to each vertex its index, we obtain a 4-z-colouring of $J_5$. Henceforth, we may assume that there is no edge between the neighbours of $d_2$ and $\{c_1, c'_1, c'_2, c'_3\}$.

Let $X$ be the set of neighbours of $d_2$ distinct from $c_3$, $Y$ the sets of neighbours of $c'_3$ distinct from $b_2$, and $Z$ the sets of neighbours of $c'_2$ distinct from $b_3$. The graph induced by $X \cup Y \cup Z$ is acyclic because $G$ has girth 7, and each of its vertices is adjacent to at most one vertex in each of $X$, $Y$, $Z$. Thus, by Lemma 29, there exist $x_1, y_1, z_1$ in $X$, $Y$, and $Z$ respectively, which are pairwise non-adjacent. Then the subgraph induced by $\{b_1, b_2, b_3, b_4, c_1, c_2, c_3, c'_1, c'_2, c'_3, d_2, x_1, y_1, z_1\}$ is the configuration $J_6$ depicted in Fig. 12. Assigning to each vertex its index, we obtain a 4-z-colouring of $J_6$.

This completes Case 5 and the proof. □

**Theorem 32.** Let $G$ be a cubic graph of girth exactly 5. If $G$ is not the Petersen graph, then $z(G) = 4$.

**Proof.** To do so, thanks to Lemma 26, it suffices to exhibit an induced subgraph of $G$ and 4-z-colouring of it, and we will do it (except in the case when $G$ is the Petersen graph).

We distinguish several cases. Note that If two 5-cycles have three consecutive or two non-consecutive edges in common, then we have a contradiction with the girth.

**Case 1** : Assume first that $G$ contains the graph $I_5$ depicted in Fig. 13 as a (necessarily induced) subgraph. For $i \in [3]$, let $c'_i$ be the neighbour of $b_i$ not in $I_5$.

**Subcase 1.1** : $c'_1$ and $c_3$ are non-adjacent. Assume first that $c'_1$ has a neighbour $d'_1$ distinct from $b_1$ and not adjacent to $c'_2$ and $b_3$. Then we are in Configuration $J_7$ depicted in Fig. 14. Set $\phi(a) = 4$, $\phi(b_2) = \phi(c'_1) = \phi(c_3) = 3$, $\phi(b_1) = \phi(c_2) = \phi(c'_3) = 2$, and $\phi(b_3) = \phi(c_1) = \phi(c'_2) = \phi(d'_1) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length at most 4 or a vertex would have degree more than 3. Hence $\phi$ is a 4-z-colouring of $J_7$.

Henceforth, the two neighbours of $c'_1$ distinct from $b_1$ are either adjacent to $c'_2$ or to $b_3$. Since there are no 4-cycle, one of them, say $d'_1$, is adjacent to $c'_2$, and the other is adjacent to $b_3$ and must be $c'_3$. Let $d_1$ be the neighbour of $c_1$ not in $I_5$.
<figure><img src="image_15.png" /><figcaption>Fig. 14. The configurations $J_7^1$ and $J_7^2$ and their 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 15. The configurations $J_7^3$ and $J_7^4$ and their 4-z-colourings. Dotted lines represent non-edges.</figcaption></figure>

If $d_1 \neq c'_3$, then we are in Configuration $J_7^2$ depicted in Fig. 14. Set $\phi(a) = 4$, $\phi(b_3) = \phi(c_1) = \phi(c'_2) = 3$, $\phi(b_1) = \phi(c_2) = \phi(c'_3) = \phi(d'_1) = 2$, and $\phi(b_2) = \phi(c'_1) = \phi(c_3) = \phi(d_1) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 4. Hence $\phi$ is a 4-z-colouring of $J_7^2$.

Henceforth, we may assume $d_1 = c'_3$. If $d'_1$ and $c_3$ are not adjacent, then we are in Configuration $J_7^3$ depicted in Fig. 15. Set $\phi(c'_3) = 4$, $\phi(b_1) = \phi(b_3) = 3$, $\phi(b_2) = \phi(c_1) = \phi(c_3) = \phi(d'_1) = 2$, and $\phi(a) = \phi(c'_1) = \phi(c_2) = \phi(c'_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 4. Hence $\phi$ is a 4-z-colouring of $J_7^3$.

If $d'_1$ and $c_3$ are adjacent, then we are in Configuration $J_7^4$ depicted in Fig. 15. Set $\phi(b_3) = 4$, $\phi(b_1) = \phi(c'_3) = \phi(d'_1) = 3$, $\phi(b_2) = \phi(c_1) = \phi(c_3) = 2$, and $\phi(a) = \phi(c'_1) = \phi(c_2) = \phi(c'_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length at most 4. Hence $\phi$ is a 4-z-colouring of $J_7^4$.

This completes Subcase 1.1.

Subcase 1.2 : $c_1$ and $c'_3$ are not adjacent. This subcase is symmetrical to Subcase 1.1.

Subcase 1.3 : $c'_1$ and $c_3$ are adjacent and $c_1$ and $c'_3$ are adjacent.

If $c'_2$ is adjacent to $c'_1$ and $c'_3$, then G is the Petersen graph, whose b-chromatic number is 3 (see [12]), so $z(G) \le 3$. Henceforth, we may assume that $c'_2$ is not adjacent to both $c'_1$ and $c'_3$. By symmetry, we may assume that $c'_1$ and $c'_2$ are not adjacent.

By Lemma 30, there is a vertex $d'_2$ distinct from $b_2$ which is adjacent to $c'_2$ and non-adjacent to $c'_3$. Thus we are in Configuration $J_7^5$ depicted in Fig. 16. Set $\phi(a) = 4$, $\phi(b_3) = \phi(c'_1) = \phi(c'_2) = 3$, $\phi(b_2) = \phi(c_1) = \phi(c_3) = 2$, and $\phi(b_1) = \phi(c_2) = \phi(c'_3) = \phi(d'_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be vertices of degree more than 3. Hence $\phi$ is a 4-z-colouring of $J_7^5$.

This completes Subcase 1.3. and Case 1.

Case 2 : Assume that G contains the graph $I_6$ depicted in Fig. 13 as a subgraph. If $c_1$ and $c_3$ are adjacent, then $I_6 - c_2$ is isomorphic to $I_5$ and we have the result by Case 1. Henceforth, we may assume that $c_1$ and $c_3$ are not adjacent, that is, $I_6$ is an induced subgraph of G. Let $c'_1$ (resp. $c'_3$) be the neighbour of $b_1$ (resp. $b_3$) not in $I_6$. Let $d_2$ be the neighbour of $c_2$ not in $I_6$ and let $d'_2$ be the neighbour of $c'_2$ not in $I_6$. If $c'_1$ is adjacent to $c'_2$ or $c_3$, then G contains $I_5$ and we have the result by Case 1. Therefore we may assume that $c'_1c'_2$ and $c'_1c_3$ are non-edges. Symmetrically, we may assume that $c'_3c_2$ and $c'_3c_1$ are non-edges.

If $d_2$ is not adjacent to $c'_3$, then we are in Configuration $J_8^1$ depicted in Fig. 17. Set $\phi(a) = 4$, $\phi(b_2) = \phi(c_1) = \phi(c_3) = 3$, $\phi(b_3) = \phi(c'_1) = \phi(c_2) = 2$, and $\phi(b_1) = \phi(c'_2) = \phi(c'_3) = \phi(d_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of G for otherwise there would be a cycle of length less than 5. Hence $\phi$ is a 4-z-colouring of $J_8^1$.
<figure><img src="image_17.png" /><figcaption>Fig. 16. The configuration $J_7^5$ and its partial 4-z-colouring. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 17. The configurations $J_8^1$ and $J_8^2$ and their partial 4-z-colourings. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 18. The configurations $J_9^1$ and $J_9^2$ and their partial 4-z-colourings. Dotted lines represent non-edges. Some edges may be missing.</figcaption></figure>

Henceforth, we may assume that $d_2c'_3$ is an edge. By symmetry, we may also assume that $d'_2c'_1$ is an edge. If $d_2$ is adjacent to $c'_1$ or $c_3$, then $G$ contains $I_5$, and we have the result by Case 1. Hence, we may assume that $d_2c'_1$ and $d_2c_3$ are non-edges. By symmetry, we may assume that $d'_2c'_3$ and $d'_2c_1$ are non-edges. Thus, we are in Configuration $J_8^2$ depicted in Fig. 17. Set $\phi(b_2) = 4$, $\phi(b_1) = \phi(c_2) = 3$, $\phi(b_3) = \phi(c'_1) = \phi(c'_2) = \phi(d_2) = 2$, and $\phi(a) = \phi(c_1) = \phi(c_3) = \phi(c'_3) = \phi(d'_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length less than 5 or a vertex of degree more than 3. Hence $\phi$ is a 4-z-colouring of $J_8^2$.

This completes Case 2.

Case 3: Assume now that we are not in Case 1 nor 2. Then any two 5-cycles do not intersect in an edge. Let $I_7 = (a, b_1, c_1, c_2, b_2, a)$ be a 5-cycle. Let $b_3$ (resp. $c'_1, c'_2, d_1$) be the neighbour of $a$ (resp. $b_1, b_2, c_1$) not in $I_7$, and let $c_3$ and $c'_3$ be the two neighbours of $b_3$ distinct from $a$. Observe that since $G$ has girth 5 and two 5-cycles do not intersect, $c_1c_2$ is the unique edge in the subgraph induced by $\{c_1, c'_1, c_2, c'_2, c_3, c'_3\}$ and $d_1$ is not in this set. By Lemma 30, $c_3$ has a neighbour $d_3$ distinct from $b_3$ which is not adjacent to $d_1$.

If $d_3$ is not adjacent to $c'_1$, then we are in Configuration $J_9^1$ depicted in Fig. 18. Set $\phi(a) = 4$, $\phi(b_1) = \phi(c_2) = \phi(c_3) = 3$, $\phi(b_3) = \phi(c_1) = \phi(c'_2) = 2$, and $\phi(b_2) = \phi(c'_1) = \phi(c'_2) = \phi(d_1) = \phi(d_3) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length less than 5. Hence $\phi$ is a 4-z-colouring of $J_9^1$.
<figure><img src="image_20.png" /><figcaption>**Fig. 19.** The graph *D* and the configuration *D*¹ and its 4-z-colouring.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>**Fig. 20.** The graph $H_1$.</figcaption></figure>

Henceforth, we may assume that $d_3$ is adjacent to $c'_1$. Let $d_2$ be the neighbour of $c_2$ which is not in $I_7$. We are in Configuration $\mathcal{J}_6$ depicted in Fig. 18. Set $\phi(a) = 4$, $\phi(b_2) = \phi(c_1) = \phi(c_3) = 3$, $\phi(b_1) = \phi(c_2) = \phi(c'_3) = \phi(d_3) = 2$, and $\phi(b_3) = \phi(c'_1) = \phi(c'_2) = \phi(d_1) = \phi(d_2) = 1$. For each $i \in [3]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length less than 5 or two intersecting 5-cycles. Hence $\phi$ is a 4-z-colouring of $\mathcal{J}_6$.

This completes Case 3 and the proof. □

**Theorem 33.** Let $G$ be a cubic graph of girth 3 with no induced 4-cycle. Then $z(G) = 4$.

**Proof.** As in the proofs of the two previous theorems, we shall exhibit an induced subgraph of $G$ and 4-z-colouring of it, which is sufficient according to Lemma 26.

**Case 1:** Assume first that $G$ contains a diamond $D$ as depicted in Fig. 19(a) as a subgraph. If $D$ is not induced in $G$, then $G$ contains a complete graph on four vertices $K_4$ whose z-chromatic number is 4. Henceforth we assume that $D$ is an induced subgraph of $G$. Let $c_i$ be the neighbour of $b_i$ which is not in $D$, for $i \in [2]$. Then, we are in configuration $D^1$. Set $\phi(a) = 4$, $\phi(c) = 3$, $\phi(b_2) = \phi(c_1) = 2$ and $\phi(b_1) = \phi(c_2) = 1$. For each $i \in [2]$, $\phi^{-1}(i)$ is a stable set of $G$ for otherwise there would be a cycle of length 4. See Fig. 19(b). Hence $\phi$ is a 4-z-colouring of $D^1$.

**Case 2:** Assume that $G$ has no diamond as a subgraph. Let $C = (a, b, c, a)$ be a 3-cycle in $G$ and let $d$ be the neighbour of $a$ which is not in $C$. Observe that $d$ is not adjacent to $b$ or $c$ because $G$ has no diamond. Let $b'$ and $c'$ be, respectively, the neighbours of $b$ and $c$ which are not in $C$. As $G$ has no induced 4-cycle, $b'$ and $c'$ are not adjacent and furthermore $d$ is not adjacent to $b'$ or $c'$. Let $d'_1$ and $d'_2$ be the neighbours of $d$ different from $a$. Hence $G$ contains the configuration $H_1$ depicted in Fig. 20 as a subgraph.

For the following subcases let $L = \{b', c'\}$ and $R = \{d'_1, d'_2\}$.

**Subcase 2.1:** Assume there is an edge $uv \in E(G)$ where $u \in L$ and $v \in R$. By symmetry, we may suppose that $u = c'$ and $v = d'_1$.

Assume first that $d'_1$ and $d'_2$ are adjacent. Then we are in the configuration $H_1^1$ depicted in Fig. 21. Set $\phi(a) = 4$, $\phi(c) = \phi(d'_2) = 3$, $\phi(d) = \phi(b') = \phi(c') = 2$, $\phi(b) = \phi(d'_1) = 1$. Then $\phi$ is a 4-z-colouring of $H_1^1$.

Assume now that $d'_1$ and $d'_2$ are not adjacent. Note that $c'$ and $d'_2$ are also not adjacent, for otherwise $\{c', d'_1, d, d'_2\}$ would induce a 4-cycle. This implies that $d'_2$ has a neighbour $f$ which is not in $H_1^1$. The vertex $f$ is not adjacent to $d'_1$, for otherwise $\{d'_1, d, d'_2, f\}$ would induce a 4-cycle. Hence we are in Configuration $H_1^2$ depicted in Fig. 21. Set $\phi(a) = 4$, $\phi(c) = \phi(d'_2) = 3$, $\phi(d) = \phi(b') = \phi(c') = 2$, $\phi(b) = \phi(d'_1) = \phi(f) = 1$. Then $\phi$ is a 4-z-colouring of $H_1^2$.

**Subcase 2.2:** There is no edge between $L$ and $R$.

Assume first that there is a vertex $f$ with a neighbour in $L$ and a neighbour in $R$. By symmetry, we may assume that $f$ is adjacent to $d'_1$ and $c'$. This implies that $f$ is not adjacent to $d'_2$ because $G$ contains no induced 4-cycle and no diamond. Hence we are in Configuration $H_1^3$ depicted in Fig. 22. Set $\phi(a) = 4$, $\phi(c) = \phi(d'_1) = 3$, $\phi(d) = \phi(b') = \phi(c') = 2$, and $\phi(b) = \phi(d'_2) = \phi(f) = 1$. Then $\phi$ is a 4-z-colouring of $H_1^3$.

Henceforth we may assume that the vertices of $L$ have no common neighbour with the vertices of $R$. Let $f$ be a neighbour of $d'_1$ that is not in $H_1$. Remark that $f$ is not adjacent to $d'_2$. The two neighbours of $c'$ distinct from $c$ are not both adjacent to
<figure><img src="image_22.png" /><figcaption>Fig. 21. The configurations $H_1^1$ and $H_1^1$ and their 4-z-colourings.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Fig. 22. Configuration $H_1^3$.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Fig. 23. Configuration $H_1^4$.</figcaption></figure>

$f$, for otherwise along with $c'$ and $f$, they would induce either 4-cycle or a diamond. Therefore, $c'$ has a neighbour $g$ distinct from $c$ which is not adjacent to $f$. Hence we are in Configuration $H_1^4$ depicted in Fig. 23. Set $\phi(a) = 4$, $\phi(c) = \phi(d_1') = 3$, $\phi(d) = \phi(b') = \phi(c') = 2$, and $\phi(b) = \phi(d_2') = \phi(f) = \phi(g) = 1$. Then $\phi$ is a 4-z-colouring of $H_1^4$.

As a cubic graph with no induced $C_4$ has girth 3 or at least 5, Theorems 31, 32, and 33 immediately imply Theorem 5.

# 6. Further research

## 6.1. Improving on the bounds for $\Gamma$ and $\chi_b$

As the z-number and the b-Grundy number are refinements of both the Grundy number and the b-chromatic number, for each of the numerous bounds known for $\Gamma$ and $\chi_b$, it is natural to ask whether a better upper bound for $z$ and $\Gamma_b$ can be obtained. It is particularly interesting bounds on $\Gamma$ and $\chi_b$ that are functions of the chromatic number $\chi$. For example, one may consider **cobipartite** graphs, which are the complements of bipartite graphs. If $G$ is cobipartite, then $\chi_b(G) \le \frac{4}{3}\chi(G)$, and this bound is tight as shown by Kouider and Zaker [17]. Hence, the following questions arise.
**Problem 34.** Does there exist a constant $\alpha < \frac{4}{3}$ such that $\Gamma_b(G) \le \alpha \cdot \chi(G)$ (resp. $z(G) \le \alpha \cdot \chi(G)$) for every cobipartite graph $G$?

Does there exist a constant $\beta < \frac{4}{3}$ such that $\chi_b(G) \le \beta \cdot \Gamma_b(G)$ (resp. $\chi_b(G) \le \beta \cdot z(G)$) for every cobipartite graph $G$?

One may also consider interval graphs. Kierstead et al. [16] proved that $\Gamma(G) \le 5\chi(G)$ for every interval graph $G$. This yields the following questions.

**Problem 35.** Does there exist a constant $\alpha < 5$ such that $\Gamma_b(G) \le \alpha \cdot \chi(G)$ (resp. $z(G) \le \alpha \cdot \chi(G)$) for every interval graph $G$?

Does there exist a constant $\beta < 5$ such that $\Gamma(G) \le \beta \cdot \Gamma_b(G)$ (resp. $\Gamma(G) \le \beta \cdot z(G)$) for every interval graph $G$?

## 6.2. Regular graphs

An approach towards **Conjecture 4** is through the girth. The **girth** of a graph is the length of a shortest cycle in $G$ (or $+\infty$ if $G$ has no cycle). It is not difficult to prove that $d$-regular graphs with sufficiently high girth have $z$-number $d+1$.

**Proposition 36.** If $G$ is a $k$-regular graph with girth at least $2k+4$, then $z(G) = k+1$.

**Proof.** Recall that there is a tree $R_k$ such that, for every tree $T$, $z(T) \ge k$ if and only if $T$ contains a subtree isomorphic to $R_k$ (Zaker [21]). The tree $R_k$ has maximum degree $k$ and diameter at most $2k+2$.

Let $G$ be a $k$-regular graph with girth at least $2k+4$. Let $v$ be a vertex of $G$. The ball $B_{k+1}(v)$ of radius $k+1$ centered at $v$ induces a complete $k$-ary tree of depth $k+1$. But the tree $R_k$ has maximum degree $k$ and diameter at most $2k+2$ and is contained in such a tree. Hence $G$ contains $R_k$ as an induced subgraph. Now $R_k$ admits a $(k+1)$-z-colouring, which can be greedily extended into a $(k+1)$-z-colouring of $G$. Hence $z(G) \ge k+1 = \Delta(G)+1 \ge z(G)$. $\square$

The bound $2k+4$ is certainly not tight. With a slightly more complicated proof one can easily prove the result for graphs with girth $2k+3$ but it is certainly not tight either. It is then natural to ask the following.

**Problem 37.** Let $k$ be an integer greater than 1.

What is the minimum integer $g_k$ such that $z(G) = k+1$ for all $k$-regular graph $G$ with girth at least $g_k$?

What is the minimum integer $g'_k$ such that $\Gamma_b(G) = k+1$ for all $k$-regular graph $G$ with girth at least $g'_k$?

**Proposition 38.** $g_2 = g'_2 = 5$.

**Proof.** It is well-known and easy to prove that $C_4$ the cycle of length 4 has Grundy number 2. Therefore $z(C_4) = \Gamma_b(C_4) = 2$, and thus $g_2, g'_2 \ge 5$.

Consider now a 2-regular graph $G$ of girth at least 5. It contains a path $P$ on 5 vertices ($x_1, x_2, x_3, x_4, x_5$). The subgraph induced by $V(P)$ is either a $C_5$ or a $P_5$. In both cases, the colouring $\phi$ defined by $\phi(x_1) = 2, \phi(x_2) = 1, \phi(x_3) = 3, \phi(x_4) = 2, \phi(x_5) = 1$ is a 3-z-colouring of $G(V(P))$, which can greedily be extended into a 3-z-colouring of $G$. Hence $3 \le z(G) = \Gamma_b(G)$. Since $\Gamma_b(G) \le \Delta(G)+1 = 3$, we get $z(G) = \Gamma_b(G) = 3$. Hence $g_2, g'_2 \le 5$. $\square$

**Theorem 5** and the fact that the Petersen graph has girth 5 and b-chromatic number 3 implies the following.

**Proposition 39.** $g_3 = g'_3 = 6$.

## 6.3. b-Grundy number and disjoint union

Consider the tree $T_b$ depicted **Fig. 2**. We have $\Gamma_b(T_b + T_b) > \Gamma_b(T_b)$. It is then natural to ask the following questions.

**Problem 40.** Does there exist a (minimum) function $h$ such that $\Gamma_b(G_1 + G_2) \le h(\Gamma_b(G_1), \Gamma_b(G_1))$?

Let $\Gamma_b^{\max}(G) = \max\{\Gamma_b(C) | C \text{ connected component of } G\}$.

**Problem 41.** Does there exist a (minimum) function $f$ such that $\Gamma_b(G) \le f(\Gamma_b^{\max}(G))$ for all graph $G$?

The following proposition implies that $f(1) = 1$ and $f(2) = 2$. The tree $T_b$ implies that $f(3) \ge 4$ (if it exists).

**Proposition 42.** If $\Gamma_b(G) \le 3$, then $\Gamma_b^{\max}(G) = \Gamma_b(G)$.

**Proof.** If $\Gamma_b(G) = 1$, then $G$ has no edge, and so $\Gamma_b^{\max}(G) = 1$.

If $\Gamma_b(G) = 2$, then $G$ contains an edge. Hence the connected component of $G$ containing this edge has b-Grundy number at least 2. Hence $\Gamma_b^{\max}(G) \ge 2 = \Gamma_b(G)$. So, by **Proposition 6**, $\Gamma_b^{\max}(G) = \Gamma_b(G) = 2$.
Assume now that $\Gamma_b(G) = 3$. Let $\phi$ be a b-greedy 3-colouring. Let $b_1$ be the b-vertex coloured 1. It has neighbours $b_3$ coloured 3, which in turn has a neighbour $b_2$ coloured 2 because $\phi$ is a greedy colouring. For the same reason, $b_2$ and $b_3$ have neighbours coloured 1. Hence each $b_i$ is a b-vertex for colour $i$. Therefore the restriction of $\phi$ to the connected component C containing $b_1, b_2, b_3$ is a b-greedy 3-colouring. Hence $\Gamma_b^{\max}(G) \ge 3 = \Gamma_b(G)$. So, by Proposition 6, $\Gamma_b^{\max}(G) = \Gamma_b(G) = 3$. $\square$

## 6.4. Computing the b-Grundy number of a tree

Lemmas 23 and 24 directly imply Corollary 25, which states that for any fixed $k$, deciding whether a given tree $T$ has b-Grundy number (resp. z-number) at least $k$ can be done in polynomial time. When $k$ is not fixed, then there is no direct implication. Indeed the time complexity of the polynomial-time algorithms for fixed $k$ are in fact $f(k) \cdot P(n)$, where $P(n)$ is a polynomial in the number $n$ of vertices of the graph and $f(k)$ is the number of $k$-atoms that can be contained in a tree. But there can potentially be a huge number of such graphs. However, Zaker [21] showed that a tree has z-number at least $k$ if and only if it contains a particular tree $R_k$. (This tree $R_k$ is the unique $k$-atom of order $(k-3)2^{k-1} + k + 2$.) This implies that computing the z-number of a tree can be done in polynomial-time.

We conjecture that the same holds for the b-Grundy number.

**Conjecture 43.** *Computing the b-Grundy number of a tree can be done in polynomial time.*

There are many different $b$-greedy $k$-atoms that can be contained in a tree. Let us call them **b-greedy k-forest-atoms** because there are forests (acyclic graphs). We believe that their number is bounded by a single exponential in $k$.

**Conjecture 44.** *There exists $\Lambda$ such that, for each positive integer $k$, the number of b-greedy k-forest-atoms is at most $\Lambda^k$.*

This would imply **Conjecture 43**. Indeed consider a tree $T$ be a tree. If $\Gamma_b(T) \ge k$, then $\Gamma(T) \ge k$ and so $T$ contains a binomial tree $B_k$ which has size $2^{k-1}$. Hence $\Gamma_b(T) \le \log n + 1$. Thus, to compute $\Gamma_b(T)$, we just need to test for all $k \in [[\log n] + 1]$ whether $\Gamma_b(T) \ge k$. But for each $k$, we just need to check whether one of the at most $\Lambda^k \le \Lambda^{\log n+1} \le \Lambda^n \log^\Lambda k$-forest-atoms is an induced subgraph of $T$, so in total, at most $\Lambda n^{\log^\Lambda (\log n+1)}$ induced subgraph tests. Each test can be done in polynomial time, so one can compute the b-Grundy number of a tree in polynomial time.

## Data availability

No data was used for the research described in the article.

## Acknowledgements

We would like to thank the two anonymous referees for their valuable comments which had improved the presentation of the paper a lot.

This research was supported by the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01.

This work was done while Jonas Costa Ferreira da Silva was spending his second year of PhD as "sandwich" in team Coati, I3S and INRIA Sophia Antipolis and this visit was funded by the project CAPES STIC-AmSud GALOP 88881.197438/2018-01.

## References

[1] M. Asté, F. Havet, C.L. Sales, Grundy number and products of graphs, Discrete Math. 310 (9) (2010) 1482-1490.

[2] T. Beyer, S.M. Hedetniemi, S.T. Hedetniemi, A linear algorithm for the Grundy number of a tree, in: Proceedings of the Thirteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, in: Utilitas Mathematica, 1982, pp. 351-363.

[3] J. Bondy, U. Murty, Graph Theory, 1st edition, Springer Publishing Company, Incorporated, 2008.

[4] S. Cabello, M. Jakovac, On the b-chromatic number of regular graphs, Discrete Appl. Math. 159 (13) (2011) 1303-1310.

[5] D.P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30 (3) (1980) 289-293.

[6] A. El Sahili, M. Kouider, M. Mortada, On the b-chromatic number of regular bounded graphs, Discrete Appl. Math. 193 (2015) 174-179.

[7] N. Gastineau, H. Kheddouci, O. Togni, On the family of r-regular graphs with Grundy number r+1, Discrete Math. 328 (2014) 5-15.

[8] F. Havet, J.C.F. da Silva, On B-Greedy Colourings and Z-Colourings, Research report, 2023, http://dx.doi.org/10.2139/ssrn.4341924, available at SSRN.; SSRN.4341924.

[9] F. Havet, A. Ibiapina, L. Rocha, On the Nash number and the diminishing Grundy number of a graph, Discrete Appl. Math. 314 (2022) 1-16.

[10] F. Havet, L. Sampaio, On the Grundy and b-chromatic numbers of a graph, Algorithmica 65 (4) (2013) 885-899.

[11] R.W. Irving, D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1) (1999) 127-141.

[12] M. Jakovac, S. Klavžar, The b-chromatic number of cubic graphs, Graphs Combin. 26 (1) (2010) 107-118.

[13] M. Jakovac, I. Peterin, The b-chromatic number and related topics? A survey, Discrete Appl. Math. 235 (2018) 184-201.

[14] R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller, J.W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103.

[15] A. Khaleghi, M. Zaker, More results on the z-chromatic number of graphs, Discrete Appl. Math. 338 (2023) 88-99.

[16] H. Kierstead, D.A. Smith, W. Trotter, First-fit coloring on interval graphs has performance ratio at least 5, European J. Combin. 51 (2016) 236-254.
[17] M. Kouider, M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math. 306 (7) (2006) 617-623.

[18] J. Kratochvíl, Z. Tuza, M. Voigt, On the b-chromatic number of graphs, in: G. Goos, J. Hartmanis, J. van Leeuwen, L. Kučera (Eds.), Graph-Theoretic Concepts in Computer Science, Springer, Berlin, Heidelberg, 2002, pp. 310–320.

[19] L. Sampaio, Algorithmic Aspects of Graph Colourings Heuristics (Thesis), Université Nice Sophia Antipolis, 2012.

[20] M. Zaker, Results on the Grundy chromatic number of graphs, Discrete Math. 306 (23) (2006) 3166-3173, International Workshop on Combinatorics, Linear Algebra, and Graph Coloring.

[21] M. Zaker, A new vertex coloring heuristic and corresponding chromatic number, Algorithmica 82 (2020) 2395-2414.

[22] D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput. 3 (6) (2007).