# The b_q-coloring of graphs

Brice Effantin

► To cite this version:

Brice Effantin. The b_q-coloring of graphs. Discrete Mathematics Letters, 2023, 12, pp.173-180.
10.47443/dml.2023.098 . hal-04315094

HAL Id: hal-04315094

https://hal.science/hal-04315094v1

Submitted on 2 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Research Article

# The b_q-coloring of graphs

Brice Effantin*

Université de Lyon, Université Claude Bernard Lyon 1, CNRS, INSA Lyon, Laboratoire d'InfoRmatique en Image et Systèmes d'information UMR 5205,
Ecole Centrale de Lyon, Université Lyon 2, F-69622 Villeurbanne, France

(Received: 22 May 2023. Received in revised form: 24 July 2023. Accepted: 9 November 2023. Published online: 27 November 2023.)

© 2023 the author. This is an open-access article under the CC BY (International 4.0) license (www.creativecommons.org/licenses/by/4.0/).

## Abstract

In this article, a new graph coloring, called the b_q-coloring, is introduced. A b_q-coloring of a graph G is a proper vertex coloring of G with k colors such that every color class c admits a set of vertices S of size at most q provided that every color except c appears in the neighborhood of S. The aim of this coloring is to generalize the domination constraint given in the b-coloring of a graph where every color admits only one dominating vertex (adjacent to every other color). The largest positive integer k for which a graph has a b_q-coloring using k colors is the b_q-chromatic number. Some classes of graphs for which the b_q-chromatic number has maximum value are presented. Also, the exact values of this parameter for paths and cycles are given. Furthermore, some bounds for Cartesian products of graphs are presented.

**Keywords:** vertex coloring; dominating coloring; complete coloring.

**2020 Mathematics Subject Classification:** 05C15.

## 1. Introduction

We consider graphs without loops or multiple edges. Let G be a graph with vertex set V(G) and edge set E(G) where |V(G)| is the order of G and |E(G)| is the size of G. In the graph G, the neighborhood of a vertex x ∈ V(G) is the set of vertices adjacent to x and it is denoted N_G(x). By extension, the neighborhood of a subset of vertices V' ⊆ V(G) is the set of vertices in V(G) \ V' adjacent to a vertex of V' (i.e. N_G(V') = ⋃_{v∈V'} N_G(v) \ V'). The degree of a vertex x is then defined by d_G(x) = |N_G(x)| and the maximum degree of the graph is Δ(G) = max{|d_G(x)| x ∈ V(G)}. If there is no ambiguity, parameters N_G(x), N_G(V) and d_G(x) are denoted respectively by N(x), N(V) and d(x).

A proper k-coloring c : V(G) → {1, 2, ..., k} of G is an assignment of colors 1, 2, ..., k to the vertices of G such that c(u) ≠ c(v) for all adjacent vertices u and v. Note that if a vertex u has a neighbor colored by c, we say that u and c are adjacent. By extension, a subset of vertices V' is adjacent to a set of colors C if every color of C is adjacent to at least one vertex of V'.

The smallest number of colors needed to have a proper coloring of a graph G is called its chromatic number and is denoted χ(G). To determine the chromatic number is an NP-complete problem for non-bipartite graphs, i.e. χ(G) ≥ 3. The parameter was intensively studied (recently [4, 11, 17]) and many derived parameters were defined. An achromatic coloring of a graph G is a proper vertex coloring of G where every pair of colors appears on at least one pair of adjacent vertices. The achromatic number of G, denoted ψ(G), is the maximum number of colors in any achromatic coloring of G. The parameter was introduced by Harary and Hedetniemi in [8] and determining the achromatic number of a graph was also proved as an NP-complete problem [20].

In a proper k-coloring, a subset of vertices D_i ⊆ V(G) such that N(D_i) contains a vertex of each color {1, 2, ..., k} \ {i} is called a dominating set for the color i. Each vertex in such a subset is a dominating vertex. A b-coloring of a graph G is a proper vertex k-coloring of G where every color i, 1 ≤ i ≤ k, admits a dominating set of size one. Such a coloring is clearly an achromatic coloring. The maximum number of colors within a b-coloring of a graph G is called the b-chromatic number and denoted ϕ(G). This coloring was introduced by Irving and Manlove [10] and they proved the NP-completeness to determine the b-chromatic number of a graph. This parameter was studied for many classes of graphs [1, 3, 5–7, 12, 14–16, 18, 19] (see [13] for a survey on this parameter).

This property of domination is very interesting because there is a privileged relation between the color classes through these dominating vertices. However, having only one dominating vertex for every color makes them very vulnerable to structure modifications of the graph. The constraint, for a vertex, to be a dominating vertex is strong and the deletion

<footnote>*E-mail address: brice.effantin-dit-toussaint@univ-lyon1.fr</footnote>
of a dominating vertex or one of its neighbors can impact the entire coloring (since determining a new dominating vertex is generally hard). In the following, we present a relaxed b-coloring of graphs where the size of dominating sets can be larger than one. Thus in Section 2 we define the b_q-coloring of a graph. We also introduce the b_q-chromatic number as the largest positive integer k for which a graph admits a b_q-coloring using k colors. In Section 3 we propose some results on this coloring. In particular, we present classes of graphs for which the b_q-chromatic number has maximum value and we prove exact values of the parameter for cycles and paths. We also propose a Nordhaus-Gaddum type inequality and some bounds of the b_q-chromatic number for Cartesian products of graphs. Finally in Section 4 we conclude and suggest further work.

## 2. The b_q-coloring of graphs

As described above, in a b-coloring of a graph the domination constraint is focused on only one vertex. We propose to generalize this coloring by relaxing the domination property to larger dominating sets. A b_q-coloring of a graph G is then defined as a proper vertex coloring of G where each color class admits a dominating set of size at most q (and at least one). The b_q-chromatic number of G, denoted $\varphi_q(G)$, is the maximum number of colors such that G admits a b_q-coloring. In a b_q-coloring, we denote the dominating set for every color i by $D_i$.

**Definition 2.1.** Let G be a graph. A b_q-coloring of G is a proper vertex k-coloring of G such that every color i, $1 \le i \le k$, admits a set of dominating vertices denoted $D_i$ where $1 \le |D_i| \le q$ and $D_i$ is adjacent to colors $\{1, 2, \dots, k\} \setminus \{i\}$.

Note that if we required at least q dominating vertices for every color, with $q > 1$, in the definition of a b_q-coloring, then such a coloring would not necessarily exist. Therefore, it is better to assume $1 \le |D_i| \le q$ and not $|D_i| \ge q$.

From this definition, we can see that such a coloring always exists since a b-coloring has dominating sets of size 1 (i.e. $\varphi_q(G) \ge \varphi_1(G) = \varphi(G)$ for $q > 1$). More generally, we have the following relation.

**Claim 2.1.** For any graph G, if $q > 1$, then $\varphi_q(G) \ge \varphi_{q-1}(G)$.

*Proof.* By Definition 2.1, a b_{q-1}-coloring of G is also a b_q-coloring of G. $\square$

By definition, the b_q-coloring of a graph is an achromatic coloring. The b_q-chromatic number can then be bounded by the achromatic and b-chromatic numbers.

**Property 2.1.** Let G be a graph. Then

$$\chi(G) \le \varphi(G) \le \varphi_q(G) \le \psi(G).$$

More particularly, the b_q-chromatic number of a graph can be upper bounded by the maximum degree of this graph.

**Theorem 2.1.** For a graph G we have $\varphi_q(G) \le q\Delta(G) + 1$.

*Proof.* Each dominating set has at most q vertices of degree $\Delta(G)$. Therefore $\varphi_q(G) \le q\Delta(G) + 1$. $\square$

A relation between the b_q-chromatic number of a graph and its stability number can also be established.

**Theorem 2.2.** Let G be a graph with stability number $\alpha$. Then $\varphi_q(G) \le n - \alpha + 1$.

*Proof.* Let S be a stable set of G of order $\alpha$. In a b_q-coloring $\mathcal{C}$ of G, p colors are used in S (colors $C = \{1, 2, \dots, p\}$ with $1 \le p \le \alpha$).

Consider $p = 1$. Since S is a maximum stable set, every vertex of $G \setminus S$ is adjacent to a vertex of S colored by 1. Thus $\varphi_q(G \setminus S) \le n - \alpha$ and $\varphi_q(G) \le n - \alpha + 1$.

Consider $p \ge 2$. We distinguish two subcases. If none of the vertices in S is a dominating vertex in $\mathcal{C}$, then at least p vertices of $G \setminus S$ are colored with the colors of C. Otherwise, let c be a color of C with a dominating vertex in S. Since S is stable, then the $p-1$ other colors of C are on vertices of $G \setminus S$. Thus from both subcases, at least $p-1$ vertices of $G \setminus S$ are colored with colors of C. The number of other colors is then at most $(n-\alpha)-(p-1)$ and we deduce $\varphi_q(G) \le n-\alpha+1$. $\square$

## 3. Some results on the b_q-chromatic number of graphs

In this section, we present some results for the b_q-chromatic number of some graphs. We present some cases for which the upper bound of the parameter is reached, in particular for regular graphs and graphs with large independent sets. Then we propose an inequality of Nordhaus-Gaddum type and we prove the exact value of the b_q-chromatic number for paths and cycles. Finally, we propose some results on the Cartesian product of graphs. We start the section with some simple graphs.
**Theorem 3.1.** Let $K_n, S_n$ and $K_{n,n'}$ be respectively a complete graph of order $n$, a stable graph of order $n$, and a complete bipartite graph with partitions of sizes $n$ and $n'$. Then we have $\varphi_q(K_n) = n$, $\varphi_q(S_n) = 1$, and $\varphi_q(K_{n,n'}) = 2$ for any $q \ge 2$.

*Proof.* The graph $K_n$ cannot be properly colored if two vertices are in the same color class. Thus we have $n$ dominating sets of size 1 and $\varphi_q(K_n) = n$.

A coloring of $S_n$ cannot have a dominating vertex for each color if it is colored with more than one color. Thus $\varphi_q(S_n) = 1$.

Finally, if a proper coloring of $K_{n,n'}$ has more than one color in a partition, these colors cannot have dominating vertices.

Thus at most one color appears in each partition and we have $\varphi_q(K_{n,n'}) = 2$.

□

We recall that $\chi(G) \ge \frac{|V(G)|}{\alpha(G)}$; see [2]. Now, we prove the following result.

**Proposition 3.1.** Let $K_{q,s}$ be a complete bipartite graph. Let $G$ be a connected $K_{q,s}$-free graph with $q \ge 2$, then $\varphi_q(G) \le (q+s-1)\chi(G) + 1 - q$.

*Proof.* For a graph $G$, we consider a $b_q$-coloring of $k$ colors where at least one dominating set $D$ has size $|D| = q$ (otherwise $\varphi_q(G) = \varphi_{q-1}(G)$). Thus there exists a set $S$ of $k-1$ neighbors of $D$ with distinct colors. Let $H$ be the subgraph induced by $D \cup S$. By hypothesis on $G$ we have $\alpha(H) \le q+s-1$. Moreover, it is clear that $\chi(H) \le \chi(G)$. Thus $k-1+q = |V(H)| \le \alpha(H) \cdot \chi(H) \le (q+s-1)\chi(G)$ and we deduce $k \le (q+s-1)\chi(G) + 1 - q$. □

□

Note that under conditions, if a graph is partially colored with a $b_q$-coloring on $k$ colors, this coloring can be extended to the whole graph without introducing new colors.

**Property 3.1.** Let $G$ be a graph. If an induced subgraph $G'$ of $G$ is $b_q$-colored with $k$ colors, and every vertex of $V(G) \setminus V(G')$ has a degree lower than $k$, then $G$ admits a $b_q$-coloring with $k$ colors.

*Proof.* For any non-colored vertex $u \in V(G)$, since its degree is $d(u) < k$, then there exists a color $c$ to properly color $u$, with $1 \le c \le k$. □

□

## Regular graphs

We can note that for graphs with a sufficiently large independent set, the upper bound of the $b_q$-chromatic number is reachable. In a graph $G$, we denote by $\text{dist}(u, v)$ the minimum distance between vertices $u$ and $v$.

**Theorem 3.2.** Let $G$ be a graph of maximum degree $\Delta$. Consider integers $q \ge 2$ and $k = q^2\Delta + q$. If $G$ contains vertices $S = \{u_1, u_2, \dots, u_k\}$ such that $d(u_i) = \Delta$ and $\text{dist}(u_i, u_j) \ge 4$, then $\varphi_q(G) = q\Delta + 1$, for every $i, j \in \{1, \dots, k\}$, $i \ne j$.

*Proof.* Consider the set of colors $\mathcal{C} = \{1, 2, \dots, q\Delta+1\}$. Let $S_i$ be the subset of $S$ defined by $S_i = \{x_{(i-1)q+1}, x_{(i-1)q+2}, \dots, x_{iq}\}$, with $1 \le i \le q\Delta+1$ (note that $\bigcup_{i=1}^{q\Delta+1} S_i = S$). We have $|N(S_i)| = q\Delta$ since the distance between two vertices of $S_i$ is at least four. Color the vertices of $S_i$ with color $i$ and the vertices of $N(S_i)$ with the $q\Delta$ other colors of $\mathcal{C}$. Due to the distance between vertices of $S$, the partial coloring of $G$ on $(q\Delta + 1)$ colors is proper, and set $S$ is a dominating set of this partial coloring. Since every non-colored vertex has a degree at most $\Delta$ it can be colored properly by Property 3.1 to have a $b_q$-coloring of $G$ where $S$ is the dominating set. Therefore $\varphi_q(G) \ge q\Delta + 1$ and by Theorem 2.1 the result holds. □

□

This property allows us to find some characteristics for regular graphs to get the upper bound for the $b_q$-chromatic number.

**Theorem 3.3.** Let $G$ be a $d$-regular graph of order $n$. If $n \ge q^2d^4$, then $\varphi_q(G) = qd + 1$, with $d \ge 3$ and $q \ge 2$ or $d = 2$ and $q \ge 4$.

*Proof.* Choose an arbitrary vertex $u_1$. Remove it and its neighbors at distance at most three. The number of removed vertices is at most $1 + d + d(d-1) + d(d-1)^2 = d^3 - d^2 + d + 1$. Repeat the operation $q(qd + 1)$ times. Thus the number of removed vertices is at most $(q^2d + q)(d^3 - d^2 + d + 1) = q^2d^4 + (q-q^2)d^3 + (q^2-q)d^2 + (q^2+q)d + q \le q^2d^4$ if $d \ge 3$ and $q \ge 2$ or $d = 2$ and $q \ge 4$. In the stable set given by the chosen vertices (each of degree $d = \Delta(G)$), the distance between each vertex is at least four and by Theorem 3.2 we deduce $\varphi_q(G) = qd + 1$. □

□

**Corollary 3.1.** Let $G$ be a $d$-regular graph of order $n$. If $n \ge q^2d^4 + 3$ with $d = 2$ and $q = 3$ (respectively if $n \ge q^2d^4 + 6$ with $d = q = 2$), then $\varphi_q(G) = qd + 1$.

*Proof.* Use the same proof as for Theorem 3.3. Remove an arbitrary vertex and its neighbors at distance at most three $(q(qd + 1)$ times) to finally remove $n_r = q^2d^4 + (q-q^2)d^3 + (q^2-q)d^2 + (q^2+q)d + q$ vertices. Since $n_r \le q^2d^4 + 3$ if $d = 2$ and $q = 3$, and $n_r \le q^2d^4 + 6$ if $d = q = 2$, then $n_r \le n$ in both cases. And since the distance between two arbitrary chosen vertices is at least four, then Theorem 3.2 gives $\varphi_q(G) = qd + 1$. □

□
## Inequality of Nordhaus-Gaddum type

**Theorem 3.4.** Let $G$ be a graph of order $n$ and $\bar{G}$ its complement. For $q \ge 2$ we have $\varphi_q(G) + \varphi_q(\bar{G}) \le n$.

*Proof.* Consider $b_q$-colorings $\mathcal{C}$ and $\bar{\mathcal{C}}$ of respectively $G$ and $\bar{G}$ with respectively $\varphi_q$ and $\bar{\varphi}_q$ colors. The dominating set of the color $i$ is denoted $D_i$ in $\mathcal{C}$ and $\bar{D}_i$ in $\bar{\mathcal{C}}$. Moreover note that every class of color $C_i$ in $\mathcal{C}$ gives a complete graph $K_{n_i}$ in $\bar{G}$, with $1 \le i \le \varphi_q$. And remark that for any dominating set $D_i$ in $\mathcal{C}$ we have $d_G(D_i) \ge \varphi_q - 1$ and $d_{\bar{G}}(D_i) \le n - \varphi_q - q + 1$. We distinguish two cases.

Suppose there exists a color $i$ such that a vertex is a dominating vertex in $\mathcal{C}$ and in $\bar{\mathcal{C}}$ (i.e. $D_i \cap \bar{D}_i \ne \emptyset$). Thus $\bar{\varphi}_q - 1 \le d_{\bar{G}}(D_i) \le n - \varphi_q - q + 1$. Therefore $\varphi_q + \bar{\varphi}_q \le n - q + 2 \le n$ since $q \ge 2$.

If for every $i$, $1 \le i \le \varphi_q$, we have $D_i \cap \bar{D}_i = \emptyset$, then the number of vertices able to be dominating vertices in $\bar{\mathcal{C}}$ is at most $n' = \sum_{i=1}^{\varphi_q} (n_i - |D_i|) \le \sum_{i=1}^{\varphi_q} (n_i - 1) \le n - \varphi_q$, where $n_i$ is the number of vertices colored with color $i$. Thus $\bar{\varphi}_q \le n' \le n - \varphi_q$ and the result holds. $\square$

## Cycles and paths

We now focus on the $b_q$-coloring of cycles. We start by presenting the following results on large cycles.

**Lemma 3.1.** If $q \ge 2$, $k = 2q + 1$ and $n = qk$, then $\varphi_q(C_n) = 2q + 1$.

*Proof.* Let $V(C_n) = \{v_1, v_2, \dots, v_n\}$. Consider the complete graph $K_k$ and let $V(K_k) = \{x_1, x_2, \dots, x_k\}$. A shortest closed walk in $K_k$ that contains every of its edges is given by solving the Chinese postman problem and this walk has length $\ell = \frac{k^2-k}{2}$ because $k$ is odd. Moreover in this walk, each vertex of $K_k$ appears $\ell/k = q$ times. Thus by traversing the $\ell$ edges of such a walk, each edge $(x_j, x_{j'})$, with $1 \le j, j' \le k$, allows to color $C_n$ by $c(v_i) = j$ where $1 \le i \le \ell = qk$. Every vertex colored by $j$ is then adjacent to two different colors and we have a $b_q$-coloring with $k$ colors where every vertex is a dominating vertex. Thus $\varphi_q(C_n) \ge 2q + 1$. Moreover Theorem 2.1 gives $\varphi_q(C_n) \le 2q + 1$ and the equality holds. $\square$

**Corollary 3.2.** If $q \ge 2$, $k = 2q + 1$ and $n \ge qk + 2$, then $\varphi_q(C_n) = 2q + 1$.

*Proof.* Let $V(C_n) = \{v_1, v_2, \dots, v_n\}$. By Lemma 3.1 there exists a $b_q$-coloring of $C_{qk}$ with $k$ colors, denoted $\mathcal{C}$. Copy the coloring $\mathcal{C}$ on the $qk$ first vertices of $C_n$, then put $c(v_{qk+1}) = c(v_1)$ and $c(v_n) = c(v_{qk})$ (note that $c(v_1) \ne c(v_{qk})$ in $\mathcal{C}$). Dominating vertices in $\mathcal{C}$ keep dominating in the partial coloring of $C_n$ and non-colored vertices have degree 2. By Property 3.1 we obtain a $b_q$-coloring of $C_n$ on $2q+1$ colors. Since Theorem 2.1 gives $\varphi_q(C_n) \le 2q+1$, the equality holds. As in Lemma 3.1, note that every dominating vertex is adjacent to two different colors. $\square$

Then we propose a construction of a $b_q$-coloring for smaller cycles.

**Lemma 3.2.** If $q \ge 2$, $k = 2q + 1$ and $qk - q \le n < qk$, then $\varphi_q(C_n) \ge 2q$.

*Proof.* Consider the cycle $C_{qk}$ and its coloring $\mathcal{C}$ on $k$ colors given by Lemma 3.1. Note that in this coloring every dominating set has size $q$ and all the vertices are dominating vertices. Thus every vertex is adjacent to two different colors. Do the following operations:

1. Remove the color $k$ from $\mathcal{C}$,

2. Remove $qk - n$ non-colored vertices (and connect their two neighbors, which have different colors),

3. Color remaining non colored vertices by Property 3.1 (they have degree 2).

Thus remaining dominating vertices given in $\mathcal{C}$ keep dominating and we have a $b_q$-coloring of $C_n$ with $k-1$ colors. Therefore $\varphi_q(C_n) \ge 2q$. $\square$

**Corollary 3.3.** If $q \ge 2$, $k = 2q + 1$ and $n = qk + 1$, then $\varphi_q(C_n) \ge 2q$.

*Proof.* Use the construction given in Lemma 3.2 to transform the coloring of $C_{qk+2}$ on $2q+1$ colors (Corollary 3.2) into a coloring for $C_n$ by removing one color and one dominating vertex of this color. As in Lemma 3.2 we see that the remaining dominating vertices from the coloring of $C_{n+1}$ keep dominating and Property 3.1 completes the coloring to have a $b_q$-coloring of $C_n$ with $2q$ colors. $\square$
Before presenting the result on cycles, we recall the following result of Harary et al. [9] on the achromatic number of cycles:

**Theorem 3.5.** [9] If $k \lfloor \frac{k-1}{2} \rfloor \le n < (k+1) \lfloor \frac{k}{2} \rfloor$, then

$$ \psi(C_n) = \begin{cases} k-1 & \text{if } n = k \lfloor \frac{k-1}{2} \rfloor + 1 \text{ and } k \text{ odd,} \\ k & \text{otherwise.} \end{cases} $$

Thus we present the exact value of the b_q-chromatic number for cycles.

**Theorem 3.6.** Let $C_n$ be a cycle of order $n \ge 3$. If $q \ge 2$ and $k = 2q + 1$, then

$$ \varphi_q(C_n) = \begin{cases} 2q+1 & \text{if } n \ge qk \text{ and } n \ne qk+1, \\ 2q & \text{if } n = qk+1 \text{ or } qk-q \le n < qk, \\ \varphi_{q-1}(C_n) & \text{if } n < qk-q. \end{cases} \quad (a) \quad (b) \quad (c) $$

*Proof.* Let $V(C_n) = \{v_1, v_2, \dots, v_n\}$.

(a) Given by Lemma 3.1 and Corollary 3.2.

(b) Consider $n = q(2q+1)+1$. Let the integer $s = 2q+1$. Since $s$ is odd and $n = s \frac{s-1}{2} + 1$, then Theorem 3.5 gives that $\psi(C_n) = s-1 = 2q$. By Property 2.1 we deduce $\varphi_q(C_n) \le \psi(C_n) = 2q$. Moreover Corollary 3.3 shows $\varphi_q(C_n) \ge 2q$. Thus the equality holds.

If $qk-q \le n < qk$, then Lemma 3.2 shows $\varphi_q(C_n) \ge 2q$. Suppose there exists a b_q-coloring of $C_n$ with $k' \ge 2q+1 = k$ colors. Since $\Delta(C_n) = 2$, then dominating sets have at least $q$ vertices and $n \ge qk' \ge qk$ which is a contradiction. Therefore $\varphi_q(C_n) \le 2q$ and the result holds.

(c) Consider $n < qk-q$. Claim 2.1 shows $\varphi_q(C_n) \ge \varphi_{q-1}(C_n)$. Suppose $\varphi_q(C_n) > \varphi_{q-1}(C_n)$. Thus there exists a dominating set $D$ such that $|D| = q$, otherwise we have a contradiction since $\varphi_q(C_n) = \varphi_{q-1}(C_n)$. Moreover every dominating vertex $x \in D$ is adjacent to at least one color not present in the neighborhood of the other dominating vertices of $D$. Indeed if every neighboring color of $x$ is also in the neighborhood of another dominating vertex of $D$, then $D' = D \setminus \{x\}$ is also a dominating set of size $|D'| < |D| = q$ and we have a contradiction too. Thus since $|D| = q$ and every dominating vertex is adjacent to a particular color, the coloring has at least $2q = k-1$ colors. Since $\Delta(C_n) = 2$, then dominating sets have at least $q$ vertices (otherwise a dominating set is adjacent to at most $2q-2$ colors). Thus we have $n \ge q(k-1)$, a contradiction. Therefore $\varphi_q(C_n) = \varphi_{q-1}(C_n)$. $\square$

We now present the exact value of the b_q-chromatic number for paths.

**Theorem 3.7.** Let $P_n$ be a path of order $n \ge 3$. If $q \ge 2$ and $k = 2q+1$, then

$$ \varphi_q(P_n) = \begin{cases} 2q+1 & \text{if } n \ge qk+2 \\ 2q & \text{if } qk-q \le n < qk+2, \\ \varphi_{q-1}(P_n) & \text{if } n < qk-q. \end{cases} \quad (a) \quad (b) \quad (c) $$

*Proof.* Let $V(P_n) = \{v_1, v_2, \dots, v_n\}$.

(a) Consider the cycle $C_n$ and its b_q-coloring on $k$ colors given by Corollary 3.2. Then remove the edge $(v_{n-2}, v_{n-1})$ to obtain the graph $P_n$. It is clear that the coloring of $C_n$ keeps a b_q-coloring of $P_n$ since neither $v_{n-1}$ nor $v_{n-2}$ is a dominating vertex. Therefore $k \le \varphi_q(P_n) \le 2q+1$ (by Theorem 2.1) and the result holds.

(b) We have $qk-q \le n < qk+2$. Consider the path $P_{qk+2}$ and its coloring given in case (a) where every dominating vertex is adjacent to two different colors. Uncolored vertices of color $k$. Remove $qk+2-n$ non-colored vertices (and connect the two neighbors of every removed vertex if it is not and endvertex of the path). Note that the remaining dominating vertices given by the initial coloring keep dominating in the partial coloring of $P_n$. Finally color remaining non-colored vertices (which have degree at most 2) by Property 3.1 to obtain a b_q-coloring on $k-1=2q$ colors for $P_n$. Thus $\varphi_q(P_n) \ge 2q$. Suppose there exists a b_q-coloring of $P_n$ with $k' \ge 2q+1$ colors. By Theorem 2.1 we have $\varphi_q(P_n) \le 2q+1$, thus $k' = k = 2q+1$. Since $k' = 2q+1$, each dominating set $D_i$ has size $q$, $1 \le i \le k'$ (due to the maximum degree 2 of vertices). If all dominating
vertices are internal vertices of $P_n$, then we have $n \ge k'|D_i| + 2 \ge (2q+1)q + 2$, a contradiction. Thus at least one endvertex of $P_n$ is a dominating vertex. Let $D$ be the dominating set containing this endvertex. Since $|D| = q$, $D$ contains also either $q-1$ internal vertices and $d(D) = 2(q-1) + 1 = 2q-1 < k' - 1$ (a contradiction to be a dominating set), or $q-2$ internal vertices and the second endvertex and $d(D) = 2(q-2) + 2 = 2q-2 < k' - 1$ (a contradiction too). Therefore no $b_q$-coloring on $k'$ colors exists and $\varphi_q(P_n) \le 2q$.

(c) Consider $n < qk - q$. We use the same reasoning as in Theorem 3.6(c). Thus Claim 2.1 shows $\varphi_q(P_n) \ge \varphi_{q-1}(P_n)$ and we suppose $\varphi_q(P_n) > \varphi_{q-1}(P_n)$. We observe that at least one dominating set $D$ has size $|D| = q$ and every dominating vertex $x \in D$ is adjacent to a unique color not present in the neighborhoods of the other dominating vertices of $D$. Thus the $b_q$-coloring of $P_n$ has at least $2q$ colors. Since $\Delta(P_n) = 2$, then dominating sets have at least $q$ vertices and $n \ge q(k-1)$, which is a contradiction. Therefore $\varphi_q(C_n) = \varphi_{q-1}(C_n)$. $\square$

## Cartesian product of graphs

The Cartesian product of two graphs $G$ and $H$, denoted $G \square H$, has the vertex set $V(G) \times V(H)$ and the neighborhood of every vertex $(x, y)$ is $N_{G \square H}((x, y)) = (x \times N_H(y)) \cup (N_G(x) \times y)$, where $x \in V(G)$ and $y \in V(H)$. Thus in the graph $G \square H$ we find several copies of graphs $G$ and $H$ denoted respectively by $G^i$ and $H^j$, with $1 \le i \le |V(H)|$ and $1 \le j \le |V(G)|$.

**Proposition 3.2.** Let $G$ and $H$ be two graphs, then $\varphi_q(G \square H) \ge \max\{\varphi_q(G), \varphi_q(H)\}$.

*Proof.* Suppose $\varphi_q(G) \ge \varphi_q(H)$. Color the vertex $(x, y)$ of $G \square H$ with $c(x) + c(y) - 1$ modulo $\varphi_q(G)$. For an edge $e = ((x_1, y_1), (x_2, y_2))$ we have $(y_1, y_2) \in E(H)$ and $y_1$ and $y_2$ have different colors in a $b_q$-coloring of $H$. Thus edge $e$ is properly colored. Similarly we can show that edges $((x_1, y), (x_2, y))$ are also properly colored. Thus the coloring of $G \square H$ is proper. Moreover, choose a copy of $G$ corresponding to a vertex $y \in V(H)$ such that $c(y) = 1$. The coloring of this copy is similar to the coloring of $G$ and the dominating sets are found. Therefore the coloring is a $b_q$-coloring of $G \square H$. $\square$

If the graphs $G$ and $H$ are bipartite, one more color can be used in a $b_q$-coloring of $G \square H$.

**Proposition 3.3.** Let $G$ be a bipartite graph. Let $P_3$ be a path of order 3. Then $\varphi_q(G \square P_3) \ge \varphi_q(G) + 1$.

*Proof.* Suppose that $G$ admits a $b_q$-coloring on $k$ colors. The proof is given by construction. Let $X$ and $Y$ be the two vertex partitions of $G$ (and respectively $X^i$ and $Y^i$ the two vertex partitions of the copy $G^i$ in $G \square H$, with $1 \le i \le 3$). Color the copy $G^2$ with the coloring of $G$. This gives dominating sets for colors 1 to $k$ denoted $D_i$ in the partial coloring, with $1 \le i \le k$. Color vertices of $Y^1$ and $X^3$ with color $k+1$. Then color vertices of $X^1$ and $Y^3$ with the coloring of respectively $X$ and $Y$ with these modifications:

* use a cyclic permutation of colors $\{1, 2, \dots, k-2, k-1\}$ to use respectively colors $\{2, 3, \dots, k-1, 1\}$,

* color $k$ is replaced by color $k+1$.

In such a coloring, note that vertices of $D_i$, $1 \le i \le k$, are adjacent to color $k+1$ either in $Y^1$ or in $X^3$. Thus every set $D_i$ is a dominating set in the final coloring. It remains to determine a dominating set for the color $k+1$. Consider the dominating set $D_k$ in $G^2$. Choose the same set called $D'$ in the graph $G' = X^3 \cup Y^1$. By construction, every vertex of $D'$ is adjacent to color $k$ in $G^2$. Moreover, since vertices of $D_k$ are adjacent to colors 1 to $k-1$ in $G^2$, then vertices of $D'$ are adjacent to colors 1 to $k$ in $G'$. Thus $D'$ is the dominating set $D_{k+1}$ for the coloring of $G \square P_3$ and $\varphi_q(G \square P_3) \ge \varphi_q(G) + 1$. $\square$

**Theorem 3.8.** Let $G$ and $H$ be two bipartite graphs with vertex partitions respectively $X_G$, $Y_G$ and $X_H$, $Y_H$. If $H$ is not a disjoint union of $K_2$, then $\varphi_q(G \square H) \ge \varphi_q(G) + 1$.

*Proof.* Let $x$ be a vertex of $X_H$ and $y_1, y_2$ be two neighbors of $x$ in $Y_H$. The induced subgraph given by vertices $\{y_1, x, y_2\}$ is a path $P_3$. Proposition 3.3 shows that $\varphi_q(G \square P_3) \ge \varphi_q(G) + 1$ and gives a coloring where $C_x$ and $C_y$ are the colorings of copies of $G$ corresponding to vertices $x$ and $y_1$ in $H$. Then for every vertex $v \in X_G$ ($v \ne x$) color the corresponding copy of $G$ in $G \square H$ by $C_x$ and for every vertex $w \in Y_G$ ($w \ne y_1, y_2$) color the corresponding copy of $G$ in $G \square H$ by $C_y$. Since $H$ is bipartite, the coloring is proper and $\varphi_q(G \square H) \ge \varphi_q(G) + 1$. $\square$

Finally, if the induced subgraphs given by dominating sets of $G$ and $H$ are stable sets with a dominating set of size one, the $b_q$-chromatic number of $G \square H$ depends on $\varphi(G)$ and $\varphi(H)$.

**Theorem 3.9.** Let $G$ and $H$ be two graphs of orders respectively $n_G$ and $n_H$. For $q \ge 2$, $G$ and $H$ have $b_q$-colorings of $k_G$ and $k_H$ colors respectively ($k_G \ge k_H$) such that the subgraphs induced by their dominating sets are stable. In the coloring of $G$ (respectively $H$) if a dominating set has size 1, then $\varphi_q(G \square H) \ge \varphi_q(G) + \varphi_q(H) - 1$.
**Proof.** Let $S_G = \{x_1, x_2, \dots, x_n\}$ (respectively $S_H = \{y_1, y_2, \dots, y_{n'}\}$) be the subset of dominating vertices in the coloring of $G$ (respectively $H$). The subset of remaining vertices is denoted $U_G = \{x_{n+1}, x_{n+2}, \dots, x_{n_G}\}$ (respectively $U_H = \{y_{n'+1}, y_{n'+2}, \dots, y_{n_H}\}$). Note that since $S_G$ and $S_H$ are stable, $S_G \square S_H$ is also stable. By hypothesis, $S_G$ (respectively $S_H$) contains a unique dominating vertex for a color $c$ (respectively $c'$), denoted $x_p$ with $1 \le p \le n$ (respectively $y_q$ with $1 \le q \le n'$). Wlog, consider in each coloring that $c = 1$ (respectively $c' = 1$).

We present a coloring for the graph $G \square H$. Let $C_1 = \{1, 2, \dots, k_G\}$ be a set of colors and $C_{k_G+1}, C_{k_G+2}, \dots, C_{k_G+k_H-1}$ be $k_H-1$ different circular permutations of $C_1$ (possible since $k_G \ge k_H$). Start by coloring the copy $G^q$ with the coloring of $G$. Then for every vertex $y_i$, with $1 \le i \ne q \le n'$, a dominating vertex for color $c$ ($1 \le c \le k_G$), color the copy $G^i$ as follows:

* the vertices of $S_G^i$ with the color $k_G + c - 1$,

* the vertices of $U_H^i$ as the set $U_G$ with the color set $C_{k_G+c-1}$ (each color class used in the coloring of $U_G$ is replaced by the corresponding color class given by $C_{k_G+c-1}$).

Note that since $S_H$ is stable, copies $G^j$ are disjointed and the partial coloring is currently proper.

From the construction sets $S_H^i$, $1 \le i \le n$, are already colored as in the initial coloring of $H$ where the initial set of colors $\{1, 2, \dots, k_H\}$ is replaced by $\{c(x_i), k_G + 1, k_G + 2, \dots, k_G + k_H - 1\}$. We complete the coloring of $H^i$ by coloring the sets $U_H^i$ with the same coloring as in $H$ by using the set of colors $\{c(x_i), k_G + 1, k_G + 2, \dots, k_G + k_H - 1\}$ (color classes in the initial coloring are replaced by the new color classes). Since the copies $H_j$ are disjointed (because $S_G$ is stable), the partial coloring is always proper. Note that $H^p$ contains colors $\{1, k_G + 1, k_G + 2, \dots, k_G + k_H - 1\}$.

It remains to color the vertices of $U_G \square U_H$. From the coloring, vertices of $U_H^p$ are colored with colors $\{1, k_G+1, k_G+2, \dots, k_G+k_H-1\}$. For each vertex $y_i \in U_H^p$, colored by $c \in \{1, k_G+1, k_G+2, \dots, k_G+k_H-1\}$, color the vertices of $U_G^i$ as the set $U_G$ with the color set $C_c$. Thus, if $c((x_p, y_i)) = 1$, then copy $G^i$ has the same coloring as $G$ and when $c((x_p, y_i)) \ge k_G + 1$, vertices of $U_G^i$ have colors 1 to $k_G$. Thus copies $G^i$, $n' \le i \le n_H$, are properly colored. Moreover, since two distinct color classes of $U_H^p$ are associated with two distinct circular permutations of $C_1$, then copies $H^j$, $n \le j \le n_G$, are also properly colored. Therefore the coloring is proper. Figure 1 illustrates the above coloring.

<figure><img src="image_2.png" /><figcaption>Figure 1: A $b_q$-coloring of $G$, $H$ and $G \square H$, where white vertices are dominating vertices.</figcaption></figure>
We now prove that the coloring is a $b_q$-coloring. Consider the set of vertices given by $D = S_G^q \cup S_H^p$. From the above construction, colors $1, 2, \dots, k_G + k_H - 1$ appear $D$ (colors $1, 2, \dots, k_G$ on $S_G^q$ and colors $k_G + 1, k_G + 2, \dots, k_G + k_H - 1$ on $S_H^p$). Furthermore, every color appears at most $q$ times in $D$ because the coloring is based on the dominating sets of $G$ and $H$. Then we check that every dominating vertex is adjacent to colors $1$ to $k_G$. Since $G^q$ is colored as $G$, then vertices of $S_G^q$ are adjacent to these colors. Moreover, since $x_p$ is the unique dominating set for color $1$ in the coloring of $G$ and colors $1$ to $k_G$ appear on $U_G^i$, $1 \le i \le n'$, then every vertex of $S_H^p$ is also adjacent to these colors. Similarly, we check that vertices of $D$ are adjacent to colors $k_G + 1$ to $k_G + k_H - 1$. Since $H^p$ is colored as $H$ with colors $\{1, k_G + 1, k_G + 2, \dots, k_G + k_H - 1\}$, then vertices of $S_H^p$ are adjacent to these colors. Moreover, since $y_q$ is the unique dominating set for color $1$ in the coloring of $H$ and colors $k_G + 1$ to $k_G + k_H - 1$ appear on $U_H^j$, $1 \le j \le n$, then every vertex of $S_G^q$ is also adjacent to these colors. Therefore we have a $b_q$-coloring of $G \square H$ where $D$ is a dominating set and $\varphi_q(G \square H) \ge \varphi_q(G) + \varphi_q(H) - 1$. $\square$

Note that the inequality of Theorem 3.9 is not obvious and we can find counterexamples. Thus we have $\varphi_1(P_2) = \varphi_2(P_2) = 2$. Then a $b_1$-coloring of $K_n \square P_2$ cannot have more than $n$ colors otherwise some colors have no dominating vertex. Thus $\varphi_1(K_n \square P_2) = \varphi_1(K_n)$ with $n \ge 3$. We can also see that $P_2 \square P_2 \equiv C_4$ and $\varphi_2(P_2 \square P_2) = \varphi_2(C_4) = 2 = \varphi_2(P_2)$.

# 4. Conclusion

A b-coloring of a graph allows to determine a dominating vertex for each color, adjacent to every other color used in the coloring. In this article, we introduced a relaxed b-coloring of graphs, called $b_q$-coloring, in order to reduce the domination constraints carried by the single dominating vertex of each color. Finding a vertex with strong constraints would be more difficult than finding several vertices with the lowest constraints to replace it. Thus the $b_q$-coloring is a proper vertex coloring whose aim is to maximize the number of colors used to color a graph by determining a dominating set of size at most $q$ for every color. We positioned the $b_q$-chromatic number relatively to other graph parameters (stability number, chromatic, and achromatic numbers). We proposed some bounds and exact values for some classical classes of graphs in particular for cycles, paths, regular graphs, and Cartesian product of graphs. Interesting questions could be to identify the values of $q$ to have $\varphi_q(G) > \varphi(G)$ or to determine the minimum integer $q$ to have $\varphi_q(G) = \psi(G)$.

Replace a unique dominating vertex with a dominating set to reduce the constraints may imply dominating sets with very different sizes. An extension of this coloring could be proposed. The equitable $b_q$-coloring of a graph could be introduced as a $b_q$-coloring for which two dominating sets would differ in size by at most one. This allows to homogenize the sizes of the dominating sets. If we denote by $\varphi_q^e(G)$ the maximum number of colors to have an equitable $b_q$-coloring of a graph $G$, we have clearly $\varphi_q^e(G) \ge \varphi_q^e(G) \ge \varphi(G)$. This second parameter could also be studied for different classes of graphs.

# Acknowledgment

The author thanks the referees for their useful suggestions that helped to improve this article.

# References

[1] R. Balakrishnan, T. Kavaskar, b-coloring of Kneser graphs, Discrete Appl. Math. 196 (2012) 9–14.

[2] C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, Amsterdam, 1984.

[3] M. Blidia, F. Maffray, Z. Zemir, On b-colorings in regular graphs, Discrete Appl. Math. 157 (2009) 1787–1793.

[4] C. Brause, B. Randerath, I. Schiermeyer, E. Vulmar, On the chromatic number of $2K_2$-free graphs, Discrete Appl. Math. 253 (2019) 14–24.

[5] V. Campos, C. L. Sales, F. Maffray, A. Silva, b-chromatic number of cacti, Electron. Notes Discrete Math. 35 (2009) 281–286.

[6] P. Francis, S. F. Raj, On b-coloring of power of hypercubes, Discrete Appl. Math. 225 (2017) 74–86.

[7] C. Guo, M. Newman, On the b-chromatic number of cartesian products, Discrete Appl. Math. 239 (2018) 82–93.

[8] F. Harary, S. Hedetniemi, The achromatic number of a graph, J. Combin. Theory 8 (1970) 154–161.

[9] F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453–462.

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

[11] A. Jafari, M. J. Moghaddamzadeh, On the chromatic number of generalized Kneser graphs and Hadamard matrices, Discrete Math. 343 (2020) #111682.

[12] M. Jakovac, S. Klavžar, The b-Chromatic Number of Cubic Graphs, Graphs Combin. 26 (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] A. Kohl, The b-chromatic number of powers of cycles, Discrete Math. Theor. Comput. Sci. 15 (2013) 147–156.

[15] M. Kouider, M. Mahéo, Some bounds for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267–277.

[16] M. Kouider, M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math. 306 (2006) 617–623.

[17] M. M. Pyaderkin, On the chromatic number of random subgraphs of a certain distance graph, Discrete Appl. Math. 267 (2019) 209–214.

[18] S. Shaebani, A note on b-coloring of Kneser graphs, Discrete Appl. Math. 257 (2019) 368–369.

[19] K. Thilagavathi, D. Vijayalakshmi, N. Roopesh, b-colouring of central graphs, Int. J. Comput. Appl. 3 (2010) 27–29.

[20] M. Yannakakis, F. Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math. 38 (1980) 364–372.