Scientific and Educational Reports of the Faculty
of Science and Technology, Kochi University
Vol. 7 (2024), No. 1
Kazuhiro Suzuki
Department of Information Science, Kochi University
Akebono-cho 2-5-1, Kochi 780-8520, Japan
要旨
A rainbow tree is an edge-colored tree whose all edges are colored with different colors. An f-chromatic tree is an edge-colored tree such that each color c appears on at most f(c) edges. A properly edge-colored graph is an edge-colored graph whose any adjacent edges are colored with different colors. An f-properly edge-colored graph is an edge-colored graph such that each vertex is incident with at most f(c) edges colored with c for any color c. In this paper, we prove that every f-properly edge-colored graph G has k edge-disjoint f+-chromatic spanning trees under the assumption that for any proper edge-coloring of G, there exist k edge-disjoint rainbow spanning trees in the properly edge-colored graph G. Here f+ is a mapping such that f+(c) = f(c)+1 for any color c. By using this theorem, we show that every f-properly edge-colored complete graph of order n (n ≧ 5) has two edge-disjoint f+-chromatic spanning trees.
Received: November 7, 2023
Reviewed by anonymous referee(s), and accepted: January 5, 2024
Published: January 24, 2024
発行者：高知大学理工学部 〒780-8520 高知県高知市曙町二丁目5-1
Faculty of Science and Technology, Kochi University, Kochi, 780-8520 Japan
問い合わせ先（E-mail）：serfst●kochi-u.ac.jp （送信の際は"●"を半角"@"に変更して送信してください）