More results on the z-chromatic number of graphs

By a z-coloring of a graph G we mean any proper vertex coloring consisting of the color classes C1, ... , Ck such that (i) for any two colors i and j with 1 < i < j < k, any vertex of color j is adjacent to a vertex of color i, (ii) there exists a set {u1, ... , uk} of vertices of G such that uj & ISIN; Cj for any j & ISIN; {1, ... , k}; also for any j = k with 1 < j < k, vertex uk is adjacent to uj and (iii) for each i and j with i = j, the vertex uj has a neighbor in Ci. Denote by z(G) the maximum number of colors used in any z-coloring of G. Denote the Grundy and b-chromatic numbers of G by & UGamma;(G) and b(G), respectively. The z-coloring is an improvement over both the Grundy and b-coloring of graphs. We prove that z(G) is much better than min{& UGamma; (G), b(G)} for infinitely many graphs G by obtaining an infinite sequence {Gn}& INFIN;n=3 of graphs such that z(Gn) = n but & UGamma; (Gn) = b(Gn) = 2n - 1 for each n & GE; 3. We show that acyclic graphs are z-monotonic and z-continuous. Then it is proved that to decide whether z(G) = increment (G) + 1 is NP-complete even for bipartite graphs G. We finally prove that to recognize graphs G satisfying z(G) = & chi;(G) is coNP-complete, improving a previous result for the Grundy number. & COPY; 2023 Elsevier B.V. All rights reserved.