On irregular colorings of graphs
2006
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) = (a0,a1,...,ak) where a0 is the color assigned to v and for 1 i k , ai 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 ir(G) of G is the minimum positive integer k for which G has an irregular k -coloring. We establish sharp upper and lower bounds for the irregular chromatic number of a disconnected graph in terms of the irregular chromatic numbers of its components. Irregular chromatic numbers of some classes of disconnected graphs are determined. It is shown that if G is a nontrivial graph of order n , then 2 p n ir(G) + ir(G) 2n , n ir(G) ir(G) n 2 , and each bound in these inequalities is sharp.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
0
References
5
Citations
NaN
KQI