2016/04/08 by Jiang, Hui, Li, Xueliang, Zhang, Yingying
#05C15 #05C40 #05C75 #05C80 #68Q17 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1604.02242
A graph is said to be \it total-colored if all the edges and the vertices of the graph are colored. A total-coloring of a graph is a \it total monochromatically-connecting coloring (\it TMC-coloring, for short) if any two vertices of the graph are connected by a path whose edges and internal vertices on the path have the same color. For a connected graph G, the \it total monochromatic connection number, denoted by tmc(G), is defined as the maximum number of colors used in a TMC-coloring of G. Note that a TMC-coloring does not exist if G is not connected, in which case we simply let tmc(G)=0. In this paper, we first characterize all graphs of order n and size m with tmc(G)=3,4,5,6,m+n-2,m+n-3 and m+n-4, respectively. Then we determine the threshold function for a random graph to have tmc(G)≥ f(n), where f(n) is a function satisfying 1≤ f(n)