Rainbow Coloring in Graphs Resulting from Cartesian Product

  • Aleffer Rocha UTFPR
  • Sheila Morais Almeida UTFPR
DOI: https://doi.org/10.5753/etc.2017.3184

Abstract


The rainbow connection number of a connected graph G, denoted by rc(G), is the minimum number of colors needed to color the edges of G, so that every pair of vertices is connected by at least one path in which the colors of the edges are pairwise distinct. In this work we determine the rainbow connection number for the graphs Cm × Pn when m is odd and Cm × Cn when m and n have distinct parities. For the case in which n and m are odd, we prove that rc(Cm × Cn) ≤ (m+n)/2.

References

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.
Published
2017-07-02
How to Cite

Select a Format
ROCHA, Aleffer; ALMEIDA, Sheila Morais. Rainbow Coloring in Graphs Resulting from Cartesian Product. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . p. 29-32. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3184.