Rainbow and Properly Colored Spanning Trees in Edge-Colored Bipartite Graphs
Tóm tắt
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.
Tài liệu tham khảo
Akbari, S., Alipour, A.: Multicolored trees in complete graphs. J. Graph Theory 54, 221–232 (2006)
Akiyama, J., Kano, M.: Factors and factorizations of graphs, LNM 2031. Springer, Berlin (2011)
Broersma, H., Tuinstra, H.: Independence trees and Hamilton cycles. J. Graph Theory 29, 227–237 (1998)
Cheng, Y., Kano, M., Wang, G.: Properly colored spanning trees in edge-colored graphs. Discret. Math. 343, 111629 (2020)
Kano, M., Maezawa, S., Ota, K., Tsugaki, M., Yashima, T.: Color degree sum conditions for properly colored spanning trees in edge-colored graphs. Discret. Math. 343, 112042 (2020)
Kano, M., Matsuda, H., Tsugaki, M., Yan, G.: Spanning \(k\)-ended trees of bipartite graphs. Discret. Math. 313, 2903–2907 (2013)
Kano, M., Ozeki, K., Suzuki, K., Tsugaki, M., Yamashita, T.: Spanning \(k\)-trees of bipartite graphs. Electron. J. Comb. 22, 1–13 (2015)
Ozeki, K., Yamashita, T.: Spanning trees—a survey. Graphs Comb. 27, 1–26 (2011)
Suzuki, K.: A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph. Graphs Comb. 22, 261–269 (2006)
Win, S.: Existenz von Gerusten mit Vorgeschiebenem Maximalgrad in Graphen. Abhandlungen aus dem Mathematichen Seminar der Universital Hamburg 43, 263–267 (1975)