Forbidden subgraphs and prohibited colorings for vertex identification in graphs

A red-white coloring of a graph [Formula: see text] of diameter [Formula: see text] is done by assigning the colors red and white to the vertices of the graph such that, there should be at least one red vertex. Then, each of the vertices is assigned a vector of length [Formula: see text] called code in which the value of [Formula: see text]th coordinate is equal to the number of red-colored vertices at distance [Formula: see text] from this vertex, [Formula: see text]. A red-white coloring when the code assigned to each vertex is different than that coloring is called an ID-coloring and a graph which has an ID-coloring is an ID-graph. The minimum number of vertices required to be colored red to get an ID-coloring is called the ID-number. ID-coloring is not possible for all graphs. There exist many properties which prevent ID-coloring. In this paper, we explore some forbidden induced subgraphs and certain prohibited red-white colorings which prevent the existence of ID-coloring.