zbMATH — the first resource for mathematics

Recognizable colorings of graphs. (English) Zbl 1235.05049
Summary: Let \(G\) be a connected graph and let \(c: V(G)\to\{1,2,\dots,k\}\) be a coloring of the vertices of \(G\) for some positive integer \(k\) (where adjacent vertices may be colored the same). 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,\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 called recognizable if distinct vertices have distinct color codes and the recognition number \(\text{rn} (G)\) of \(G\) is the minimum positive integer \(k\) for which \(G\) has a recognizable \(k\)-coloring. Recognition numbers of complete multipartite graphs are determined and characterizations of connected graphs of order \(n\) having recognition numbers \(n\) or \(n-1\) are established. It is shown that for each pair \(k,n\) of integers with \(2\l\leq n\), there exists a connected graph of order \(n\) having recognition number \(k\). Recognition numbers of cycles, paths, and trees are investigated.

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI Link