zbMATH — the first resource for mathematics

Irregular colorings of some graph classes. (English) Zbl 1177.05035
The authors consider proper \(t\)-colorings \(c\) of the vertices of graphs \(G\), i.e. adjacent vertices are assigned different colors of a color set \(\{0,1,\dots, t-1\}\). The neighbourhood color code of a vertex \(v\) with respect to the coloring \(c\) of \(G\) is a \(t\)-tuple \(v^c= (\dots,v^c_k,\dots)\) whose \(k\)th component \(v^c_k\) is the number of vertices adjacent to \(v\) and and colored with \(k\) for every \(k\in\{0,1,\dots, t-1\}\). An irregular \(t\)-coloring of \(G\) is a proper coloring \(c\) such that \(c(x)= c(y)\) implies \(x^c\neq y^c\). The irregular chromatic number is the smallest \(t\) for which there is an irregular \(t\)-coloring of \(G\).
The authors prove two conjectures of Radcliffe and Zhang. They determine the irregular chromatic number of cycles \(C_n\), paths \(P_n\) and of \(K_m\times K_n\), extending results of Okamoto, Radcliffe and Zhang.

05C15 Coloring of graphs and hypergraphs