Coloração arco-íris em grafos resultantes de produto cartesiano

• Aleffer Rocha UTFPR
• Sheila Morais Almeida UTFPR

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

Resumo

O número de conexão arco-íris de um grafo conexo G, denotado por rc(G), é o menor número de cores necessárias para colorir as arestas de G, de forma que entre qualquer par de vértices exista um caminho cujas cores das arestas são duas a duas distintas. Neste trabalho determinamos o número de conexão arco-íris para os grafos C_m × P_n quando m é ímpar e C_m × C_n quando m e n têm paridades distintas. Para os casos em quem e n são ímpares, provamos que rc(C_m × C_n) ≤ (m+n)/2.

Referências

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

Chandran, L. S., Das, A., Rajendraprasad, D., and Varma, N. M. (2012). Rainbow connection number and connected dominating sets. Journal of Graph Theory, 71:206–218.

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

Li, X., Liu, S., Chandran, L. S., Mathew, R., and Rajendraprasad, D. (2012). Rainbow connection number and connectivity. Electronic Notes of Combinatorics, 19(1). P20.

Li, X., Shi, Y., and Sun, Y. (2013). Rainbow connections of graphs: A survey. Graphs and Combinatorics, 29(1):1–38.