Sobre a 4-atribuição de papéis para produto forte de grafos

Uma 𝑟-atribuição de papéis em um grafo 𝐺 consiste em rotular os vértices com 𝑟 papéis distintos de forma que vértices com o mesmo papel tenham o mesmo conjunto de papéis nos vértices adjacentes. O problema de atribuição de papéis possui aplicações em redes sociais, biológicas e tecnológicas. É conhecido que determinar se um grafo admite 𝑟-atribuição de papéis é NP-completo para 𝑟 ≥ 2. Neste artigo, investigamos o problema da 4-atribuição de papéis no produto forte de grafos 𝐺 ⊠ 𝐻. Provamos que o problema é NP-completo quando 𝐺 e 𝐻 são grafos não triviais. Por outro lado, mostramos que, quando 𝐺 ou 𝐻 são bipartidos, cografos, grafos split, ou cordais com 2-atribuição de papéis, o produto forte entre eles sempre admite uma 4-atribuição de papéis, o que torna o problema solucionável em tempo constante ou linear no caso dos cordais.