Multicolorful connectivity of trees

作者：

Highlights：

• The connectivity of graphs is always an important parameter in graph the- ory. During the last decade, it is an active topic to study the connectivity of edge-colored graphs. The rainbow connectivity is the most well-known such problem and there are fruitful results about the rainbow connectivity of graphs. Notice that the color version of the graph connectivity can be used to characterize the property of networks and hence these problems are very meaningful.

• In 2011, Caro and Yuster introduced the colorful monochromatic connectivity of graphs, which considers the maximum number of colors used in an edge-coloring of a graph such that for any two vertices, there is a monochromatic path joining them. In this paper, we replace the condition monochromatic path with the path with at most $k$ colors and determine the color number for trees exactly. Also, we study the problem for unicyclic graphs and we get some basic results for it.

摘要

•The connectivity of graphs is always an important parameter in graph the- ory. During the last decade, it is an active topic to study the connectivity of edge-colored graphs. The rainbow connectivity is the most well-known such problem and there are fruitful results about the rainbow connectivity of graphs. Notice that the color version of the graph connectivity can be used to characterize the property of networks and hence these problems are very meaningful.•In 2011, Caro and Yuster introduced the colorful monochromatic connectivity of graphs, which considers the maximum number of colors used in an edge-coloring of a graph such that for any two vertices, there is a monochromatic path joining them. In this paper, we replace the condition monochromatic path with the path with at most $k$ colors and determine the color number for trees exactly. Also, we study the problem for unicyclic graphs and we get some basic results for it.

论文关键词：Coloring,Tree,Connectivity

论文评审过程：Received 7 December 2020, Revised 10 February 2021, Accepted 27 February 2021, Available online 13 March 2021, Version of Record 13 March 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126147