On irregular colorings of graphs (Q2370393)

A proper vertex coloring \(c:V(G)\rightarrow \{1,\dots,k\}\) of a graph \(G\) is ``irregular'' if for every pair of vertices \(v\neq w\) with \(c(v)=c(w)\), there is some \(i\in \{1,\dots,k\}\) such that \(v\) and \(w\) have different numbers of neighbors colored \(i\). The irregular chromatic number \(\chi _{ir}(G)\) is the smallest value of \(k\) for which \(G\) has such a vertex coloring. The authors provide upper and lower bounds for the irregular chromatic number of a disconnected graph: if \(G\) is the union of pairwise disjoint subgraphs \(G_{1},\dots,G_{p}\) then \(\max \{\chi _{ir}(G_{1}),\dots,\chi _{ir}(G_{p})\}\leq \chi _{ir}(G)\leq \sum_{j=1}^{p}\chi _{ir}(G_{j})\). The lower bound is always attained if there are no \(j\neq j^{\prime }\) such that \(G_{j}\) contains a vertex with the same degree as some vertex of \(G_{j^{\prime }}\). The upper bound can be sharpened if one knows how many isolated vertices are contained in the \(G_{j}\), and is attained precisely when each \(G_{j}\) contains \(\chi _{ir}(G_{j})\) isolated vertices. The authors also verify the following analogues of the Nordhaus-Gaddum inequalities [\textit{E. A. Nordhaus} and \textit{J. W. Gaddum}, Am. Math. Mon. 63, 175-177 (1956; Zbl 0070.18503)], if \(G\) is a graph of order \(n\) and \(\overline{G}\) is the complement of \(G\) then \(2\sqrt{n}\leq \chi _{ir}(G)+\chi _{ir}(\overline{G})\leq 2n\) and \(n\leq \chi _{ir}(G)\chi _{ir}(\overline{G})\leq n^{2}\). They observe that the upper bounds are attained only by complete graphs and their complements, and they provide examples that realize the lower bounds; they also observe that if \(G\) is of order \(n\) and \(\chi _{ir}(G)=2\), then \(n/2\leq \chi _{ir}(\overline{G })\leq (n+2)/2\). The paper closes with a discussion of the irregular chromatic numbers of disconnected graphs whose components are complete multipartite graphs.