On the Irregular Chromatic Number of a Graph

摘要

For a graph G and a proper coloring c : V(G) → {1,2,...,k} 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 code(v) = (a_0, a_1,... ,a_k), where a_0 is the color assigned to v and, for 1 ≤ i ≤ k, a_i is the number of the vertices of G adjacent to v that are colored i. The coloring c is irregular if distinct vertices have distinct color codes and the irregular chromatic number χ_(ir) (G) of G is the minimum positive integer k for which G has an irregular k-coloring. We study irregular colorings of cycles and trees. The irregular chromatic numbers of the cycle and path of order n are determined for 3 < n < 100. For each integer n ≥ 2, let D_T{n) and d_T(n) be the maximum and the minimum irregular chromatic numbers among all trees of order n, respectively. It is shown that D_t(n) = n and the values of d_T(n) are determined for 3 ≤ n ≤ 100. We investigate how the irregular chromatic number of a graph can be affected by removing a vertex or an edge from the graph. Also, we survey the results, conjectures, and problems on this topic.