Geodesic
Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1023-1036

Voir la notice de l'article provenant de la source Library of Science

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 total-connected. 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 Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k.
Keywords: Rainbow total-coloring, rainbow total-connection number, complementary graph, Erdős-Gallai type problem 
@article{DMGT_2018_38_4_a10,
     author = {Sun, Yuefang and Jin, Zemin and Tu, Jianhua},
     title = {Rainbow {Total-Coloring} of {Complementary} {Graphs} and {Erd\H{o}s-Gallai} {Type} {Problem} {For} {The} {Rainbow} {Total-Connection} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1023--1036},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/}
}
TY  - JOUR
AU  - Sun, Yuefang
AU  - Jin, Zemin
AU  - Tu, Jianhua
TI  - Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 1023
EP  - 1036
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/
LA  - en
ID  - DMGT_2018_38_4_a10
ER  - 
%0 Journal Article
%A Sun, Yuefang
%A Jin, Zemin
%A Tu, Jianhua
%T Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 1023-1036
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/
%G en
%F DMGT_2018_38_4_a10
Sun, Yuefang; Jin, Zemin; Tu, Jianhua. Rainbow Total-Coloring of Complementary Graphs and Erdős-Gallai Type Problem For The Rainbow Total-Connection Number. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1023-1036. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a10/