Color degree sum conditions for properly colored spanning trees in edge-colored graphs

被引:1
作者
Kano, Mikio [1 ]
Maezawa, Shun-ichi [2 ]
Ota, Katsuhiro [3 ]
Tsugaki, Masao [4 ]
Yashima, Takamasa [3 ,5 ]
机构
[1] Ibaraki Univ, Hitachi, Ibaraki, Japan
[2] Yokohama Natl Univ, Yokohama, Kanagawa, Japan
[3] Keio Univ, Yokohama, Kanagawa, Japan
[4] Tokyo Univ Sci, Tokyo, Japan
[5] Seikei Univ, Tokyo, Japan
关键词
Edge-colored graph; Spanning tree; Properly colored; Rainbow;
D O I
10.1016/j.disc.2020.112042
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a vertex v of an edge-colored graph, the color degree of v is the number of colors appeared in edges incident with v. An edge-colored graph is called properly colored if no two adjacent edges have the same color. In this paper, we prove that if the minimum color degree sum of two adjacent vertices of an edge-colored connected graph G is at least vertical bar G vertical bar, then G has a properly colored spanning tree. This is a generalization of the result proved by Cheng, Kano and Wang. We also show the sharpness of this lower bound of the color degree sum. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数:5
相关论文
共 7 条
[1]   Multicolored trees in complete graphs [J].
Akbari, S. ;
Alipour, A. .
JOURNAL OF GRAPH THEORY, 2007, 54 (03) :221-232
[2]   Properly colored spanning trees in edge-colored graphs [J].
Cheng, Yangyang ;
Kano, Mikio ;
Wang, Guanghui .
DISCRETE MATHEMATICS, 2020, 343 (0I)
[3]  
Dirac G.A., 1952, Proc. Lond. Math. Soc., V2, P69, DOI [DOI 10.1112/PLMS/S3-2.1.69, 10.1112/plms/s3-2.1.69]
[4]   Rainbow C3's and C4's in edge-colored graphs [J].
Li, Hao .
DISCRETE MATHEMATICS, 2013, 313 (19) :1893-1896
[5]   Color Degree Sum Conditions for Rainbow Triangles in Edge-Colored Graphs [J].
Li, Ruonan ;
Ning, Bo ;
Zhang, Shenggui .
GRAPHS AND COMBINATORICS, 2016, 32 (05) :2001-2008
[6]  
Ore O., 1960, Am Math Monthly, V67, P55, DOI [10.2307/2308928, DOI 10.2307/2308928]
[7]   A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph [J].
Suzuki, Kazuhiro .
GRAPHS AND COMBINATORICS, 2006, 22 (02) :261-269