3-atribuição de papéis em produto forte de grafos bipartidos e grafos cordais sem folhas

• Gustavo Morais Medeiros UFG
• Julliano Rosa Nascimento UFG

DOI: https://doi.org/10.5753/etc.2024.2890

Resumo

Seja G um grafo simples e r um inteiro positivo. Uma r-atribuição de papéis é uma atribuição de r papéis distintos aos vértices de G, tal que, dois vértices com o mesmo papel têm o mesmo conjunto de papéis nos vértices adjacentes. Determinar se um grafo possui uma r-atribuição de papéis é NP-completo para r ≥ 3 fixo, mesmo restrito a grafos bipartidos ou cordais. Motivados por trabalhos anteriores, mostramos que o produto forte entre dois grafos conexos não triviais possui uma 3-atribuição de papéis se ao menos um de seus fatores for um grafo bipartido ou for um grafo cordal sem folhas.

Referências

Aleksandar, P. e Fred, R. (1999). The role assignment model nearly fits most social networks. Mathematical Social Sciences, 41(3):275–293.

Bondy, J. A. e Murty, U. S. R. (2008). Graph theory. Springer Publishing Company, Incorporated.

Castonguay, D., Dias, E. S., Mesquita, F. N., e Nascimento, J. R. (2022). Computing some role assignments of cartesian product of graphs. RAIRO-Oper. Res., 56(1):115–121.

Castonguay, D., Dias, E. S., Mesquita, F. N., e Nascimento, J. R. (2023). Computing role assignments of cartesian product of graphs. RAIRO-Oper. Res., 57(3):1075–1086.

Diestel, R. (2000). Graph theory. New York, USA, Springer-Verlag.

Dourado, M. C. (2016). Computing role assignments of split graphs. Theoretical Computer Science, 635:74–84.

Fiala, J. e Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical computer science, 349(1):67–81.

Hammack, R. H., Imrich, W., e Klavžar, S. (2011). Handbook of product graphs, volume 2. CRC press Boca Raton.

Medeiros, G. M. e Nascimento, J. R. (2023). O produto forte de um grafo não trivial e o grafo completo possui 2-e 3-atribuição de papéis. In Anais da XI Escola Regional de Informática de Goiás. SBC.

Pandey, S. (2019). Role colouring hereditary classes of graphs. PhD thesis, Indian Institute of Science Education and Research Pune.

Purcell, C. e Rombach, P. (2015). On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms, 35:1–8.

Purcell, C. e Rombach, P. (2021). Role colouring graphs in hereditary classes. Theoretical Computer Science, 876:12–24.

van ’t Hof, P., Paulusma, D., e van Rooij, J. M. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40):3601–3613.

Zhao, Y.-q., Feng, W.-l., Li, H., e Yang, J.-m. (2010). k-role assignments under some graph operations. Journal of Hebei University of Science and Technology, page 06.