Exploring Adjacency Recognizable Colorings in Graphs: A New Variant of Adjacency Codes

Abstract

Let G be a nontrivial connected graph and c : V(G) → {1, 2, ..., k} be a coloring of G, where adjacent vertices may be colored the same. For any vertex v of G, the adjacency code ad_c(v) of v with respect to c is defined as the ordered k-tuple , where  is the number of vertices adjacent to v that are colored i for 1 ≤ i ≤ k. The coloring c is called adjacency recognizable if distinct vertices have distinct adjacency codes, and the adjacency recognition number of G, denoted an(G), is the minimum positive integer k for which G admits an adjacency recognizable k-coloring. This study examines the relationships between the recognition number and the adjacency recognition number of a graph, with the novelty that adjacency recognizable colorings are based only on the colors of neighboring vertices, excluding the vertex itself, and do not require proper colorings, leading to new behaviors and existence conditions. Our findings indicate that adjacency recognition numbers are not defined for certain graphs. In addition, the bounds of an(G) are presented in terms of the order of G, depending on its diameter.