Rainbow total-coloring of complementary graphs and Erdos-Gallai type problem for the rainbow total-connection number
Zemin Jin, Yuefang Sun, Jianhua Tu · Discussiones Mathematicae Graph Theory · 2018
A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow totalconnected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam(G) = 2, diam(G) = 3, G contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erds-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f (n, k),