More results on the \(z\)-chromatic number of graphs (Q6110594)

This paper studies proper colourings of graphs (we regard the colours as positive integers so having a natural order on them). In addition to the chromatic number \(\chi(G)\), two quantities which are often considered are the Grundy number \(\Gamma(G)\), i.e. the largest possible number of colours which can be used in a proper colouring with the additional property that, given \(j>i\) colours, every vertex of colour \(j\) is adjacent to a vertex of colour \(i\). It is easy to see by colouring greedily that \(\chi(G)\leq \Gamma(G)\leq \Delta(G)+1\) where \(\Delta\) is the maximum degree. Also studied is the \(b\)-chromatic number \(b(G)\), the largest number of colours in a proper colouring with the property that every colour class contains a vertex which is adjacent to a vertex in every other class. Again, a greedy colouring argument shows that \(\chi(G)\leq b(G)\leq \Delta(G)+1\). There is no simplistic relationship between \(\Gamma(G)\) and \(b(G)\) though some partial results are known. The main business of the paper under review is to examine a third variant of the chromatic number, the \(z\)-chromatic number. A \(z\)-colouring is a proper colouring with colour classes \(C_{1},\ldots, C_{k}\) such that for colours \(1\leq i<j\leq k\) any vertex of colour \(j\) is adjacent to one of colour \(i\) and there exists a set \(\{u_{1},\ldots, u_{k}\}\) of vertices, with \(u_{i}\in C_{i}\) for all \(1\leq i\leq k\), for any \(1\leq j<k\) we have \(u_{j}\) is adjacent to \(u_{k}\) and for \(j\neq i\), \(u_{j}\) has a neighbour in \(C_{i}\). The \(z\)-chromatic number is the largest number of colours which can be used in a \(z\)-colouring. The point is that \(\chi(G)\leq z(G)\leq \min\{b(G),\Gamma(G)\}\) suggesting the possibility of getting better upper bounds on \(\chi(G)\) from such colourings. The paper is devoted to a number of results on the \(z\)-chromatic number. First of all, it is noted that \(z\)-chromatic number is not \(z\)-continuous; that is that there are infinitely many graphs for which for some value of \(k\) between \(\chi(G)\) and \(z(G)\) there is not a \(z\)-colouring with \(k\) colours. A further snag is that \(z\)-chromatic number is not \(z\)-monotone; there are infinitely many graphs which do not have the property that for every induced subgraph \(H_{1}\) of \(G\) and every induced subgraph \(H_{2}\) of \(H_{1}\), we have \(z(H_{1})\geq z(H_{2})\). However, the authors do manage to prove a result about the \(z\)-chromatic number of the join and union of two graphs. They also provide some support for the idea of using \(z\)-chromatic number to get better bounds on the chromatic number by exhibiting an infinite sequence of graphs \((G_{n})\) with \(b(G_{n})=\Gamma(G_{n})=2n-1\) but \(z(G_{n})=\chi(G_{n})=n\). In contrast to the general case in the previous paragraph, it is shown that acyclic graphs are \(z\)-continuous and \(z\)-monotone. Finally, the focus turns to complexity and it is shown that deciding whether or not \(z(G)=\Delta(G)+1\) is NP-complete, even for bipartite graphs \(G\) and that recognising graphs with \(z(G)=\chi(G)\) is coNP-complete.