On Rainbow Coloring of Quadrilateral Snake Graphs

• Felipe B. Wendt IFPR
• Aleffer Rocha IFPR / UFPR
• M. M. Omai CEFET-RJ

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

Resumo

A path is said rainbow if its edges have pairwise distinct colors. A graph G admits a rainbow coloring if there exists a rainbow path between every pair of vertices of G. When such a path is a shortest path, we say that G has a strong rainbow coloring. The rainbow connection number rc(G) (respectively, the strong rainbow connection number src(G)) is the minimum number of colors required to obtain a (strong) rainbow coloring of G. In this work, we determine rc(G) and src(G) when G is a quadrilateral snake graph. We also determine rc(G) when G is a double quadrilateral snake graph.

Referências

Ananth, P., Nasre, M., and Sarpatwar, K. K. (2011). Rainbow connectivity: Hardness and tractability. In Chakraborty, S. and Kumar, A., editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), volume 13 of Leibniz International Proceedings in Informatics (LIPIcs), pages 241–251, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Chakraborty, S., Fischer, E., Matsliah, A., and Yuster, R. (2011). Hardness and algorithms for rainbow connection. Journal of Combinatorial Optimization, 21(3):330–347.

Chartrand, G., Johns, G. L., McKeon, K. A., and Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98.

Li, S., Li, X., and Shi, Y. (2015). Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs. Applied Mathematics and Computation, 258:155–161.

Li, X. and Sun, Y. (2012). Rainbow Connections of Graphs. Springer US.

Ma, Y., Xue, Y., and Zhang, X. (2025). Proper (strong) rainbow connection and proper (strong) rainbow vertex connection of graphs with large clique number. Journal of Interconnection Networks, 25(01):2350034.

Ma, Y. and Zhao, Y. (2025). Some results on (1,2)-rainbow connection number. Discrete Applied Mathematics, 373:231–238.

Rocha, A. (2020). Coloração arco-íris em classes de grafos. Master thesis. Federal University of Technology – Paraná (UTFPR), Ponta Grossa.

Rocha, A., Almeida, S., and Zatesko, L. (2020a). The rainbow connection number of triangular snake graphs. In Anais do V Encontro de Teoria da Computação, pages 65–68, Porto Alegre, RS, Brasil. SBC.

Rocha, A., Almeida, S. M., and Zatesko, L. M. (2020b). A near-tight bound for the rainbow connection number of snake graphs. In Proc. IX Latin American Workshop on Cliques in Graphs (LAWCG ’20), page 12.

Rocha, A., Almeida, S. M., and Zatesko, L. M. (2022). Rainbow connectivity and rainbow criticality on graph classes. Discrete Applied Mathematics, 323:311–323. LAGOS’19 - X Latin and American Algorithms, Graphs, and Optimization Symposium - Belo Horizonte, Minas Gerais, Brazil.

Yulianti, L., Nazra, A., et al. (2025). On the rainbow connection numbers of line, middle, and total graphs of wheels. Electronic Journal of Graph Theory & Applications, 13(1).