Coloração de identificação local em algumas classes de grafos

Abstract

locally identifying coloring (lid-coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the sets of colors used on the vertices of the closed neighborhoods of u and v are distinct. The locally identifying chromatic number (lid-chromatic number) of a graph G, denoted by χlid(G), is the minimum number of colors required in any lid-coloring of G. We studied locally identifying colorings of powers of paths graphs. We investigate lid-colorings in split graphs and in subclasses such as complete split graphs and split-comparability graphs, obtaining exact values and bounds for the lid-chromatic number in these classes. In addition, we show that the problem of deciding whether a split graph admits a lid-coloring with a given number of colors is NP-complete. Next, we study lid-colorings in the corona product of graphs. In this context, besides structural results and bounds, we prove that the problem of deciding the existence of a lid-coloring in graphs obtained through the corona product is also NP-complete. We also determined exact values of the lid-chromatic number of the corona product for several families, including cases in which the factors are paths, cycles, complete graphs, and complements of complete graphs. We also establish lower and upper bounds for the lid-chromatic number in more general cases. Finally, we study the lid-chromatic number of the Cartesian product of a complete graph with a path. Moreover, we provide lower and upper bounds for graphs obtained from the Cartesian product between a complete graph and a cycle, as well as between two complete graphs.