Paper Info
Title
Rainbow and Properly Colored Spanning Trees in Edge-Colored Bipartite Graphs
Abstract
An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp.
Year
DOI
Venue
2021
10.1007/s00373-021-02334-5
GRAPHS AND COMBINATORICS
Keywords
DocType
Volume
Edge-colored bipartite graph, Bipartite graph, Rainbow spanning tree, Properly colored spanning tree
Journal
37
Issue
ISSN
Citations 
5
0911-0119
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Mikio Kano154899.79
Masao Tsugaki23213.71