On z-coloring and ${\mathrm{b}}^{\ast }$-coloring of graphs as improved variants of the b-coloring

Abstract

Let $G$ be a simple graph and $c$ a proper vertex coloring of $G$. A vertex $u$ is called b-vertex in $(G,c)$ if all colors except $c(u)$ appear in the neighborhood of $u$. By a ${\mathrm{b}}^{\ast }$-coloring of $G$ using colors $\{1,\dots ,k\}$ we define a proper vertex coloring $c$ such that there is a b-vertex $u$ (called nice vertex) such that for each $j\in \{1,\dots ,k\}$ with $j\ne c(u)$, $u$ is adjacent to a b-vertex of color $j$. The ${\mathrm{b}}^{\ast }$-chromatic number of $G$ (denoted by ${\mathrm{b}}^{\ast }(G)$) is the largest integer $k$ such that $G$ has a ${\mathrm{b}}^{\ast }$-coloring using $k$ colors. Every graph $G$ admits a ${\mathrm{b}}^{\ast }$-coloring which is an improvement over the famous b-coloring. A z-coloring of $G$ is a coloring $c$ using colors $\{1,2,\dots ,k\}$ containing a nice vertex of color $k$ such that for each two colors $i<j$, each vertex of color $j$ has a neighbor of color $i$ in the graph (i.e. $c$ is obtained from a greedy coloring of $G$). We prove that ${\mathrm{b}}^{\ast }(G)$ cannot be approximated within any constant factor unless $P=NP$. We obtain results for ${\mathrm{b}}^{\ast }$-coloring and z-coloring of block graphs, cacti, $P_4$-sparse graphs and graphs with girth greater than $4$. We prove that z-coloring and ${\mathrm{b}}^{\ast }$-coloring have a locality property. A linear 0-1 programming model is also presented for z-coloring of graphs. The positive results suggest that researches can be focused on ${\mathrm{b}}^{\ast }$-coloring (or z-coloring) instead of b-coloring of graphs.

17 pages, 2 figures