# 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.)
##### Keywords:
recognizable coloring; recognition number
Full Text: