×

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.

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