zbMATH — the first resource for mathematics

Irregular colorings of graphs. (English) Zbl 1119.05047
Let \(G\) be a connected graph and let \(c: V(G)\to\{1,2,\dots, k\}\) be a proper coloring of the vertices of \(G\) for some positive integer \(k\). The color code of a vertex \(v\) of \(G\) (with respect to \(c\)) is the ordered \((k+1)\)-tuple \(\text{code}(v)= (a_0,a_1,\dots, a_k)\) where \(a_0\) is the color assigned to \(v\) and for \(1\leq i\leq k\), \(a_i\) is the number of vertices adjacent to \(v\) that are colored \(i\). The coloring \(c\) is irregular if distinct vertices have distinct color codes and the irregular chromatic number number \(\chi_{ir}(G)\) of \(G\) is the minimum positive integer \(k\) for which \(G\) has an irregular \(k\)-coloring.
It is easy to show that if \(G\) is a nontrivial connected graph of order \(n\), then \(2\leq\chi_{ir}(G)\leq n\). The authors characterize those graphs with irregular chromatic number 2 or \(n\). In order to do this they make the following definition. For each even integer \(n= 2k\), where \(k\) is a positive integer, \(F_n\) is the bipartite graph with partite sets \(X= \{x_1, x_2,\dots, x_k\}\) and \(Y= \{y_1, y_2,\dots, y_k\}\) such that \(\deg x_i= \deg y_i\) for \(1\leq i\leq k\).
Theorem 1. Let \(G\) be a connected graph of order \(n\geq 2\). Then \(\chi_{ir}(G)= 2\) if and only if \(n\) is even and \(G\cong F_n\).
Theorem 2. Let \(G\) be a connected graph of order \(n\). Then \(\chi_{ir}(G)= n\) if and only if \(G\) is a complete multipartite graph.
The authors also obtain the following result.
Theorem 3. For every pair \(k\), \(n\) of integers with \(3\leq k\leq n\), there exists a connected graph of order \(n\) having irregular chromatic number \(k\).
Finally, the authors investigate the irregular chromatic numbers of cycles.

05C15 Coloring of graphs and hypergraphs