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.

MSC:
 05C15 Coloring of graphs and hypergraphs