Scientific and Educational Reports of the Facultyof Science and Technology, Kochi UniversityVol. 7 (2024), No. 1

A note on f +-chromatic spanning trees
in f -properly edge-colored graphs
Kazuhiro Suzuki∗

Abstract
A rainbow tree is an edge-colored tree whose all edges are colored withdifferent colors. An f -chromatic tree is an edge-colored tree such that eachcolor c appears on at most f (c) edges. A properly edge-colored graph isan edge-colored graph whose any adjacent edges are colored with differentcolors. An f -properly edge-colored graph is an edge-colored graph such thateach 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 hask edge-disjoint f + -chromatic spanning trees under the assumption that forany 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 thatf + (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.

We consider finite undirected graphs without loops or multiple edges. For agraph G, let V (G) and E(G) denote its vertex and edge sets, respectively. For agraph G and a set C of colors, let color be a mapping from E(G) to C. Then, themapping color is called an edge-coloring of G, and the triple (G, C, color) is calledan edge-colored graph. We often abbreviate an edge-colored graph (G, C, color) asG. An edge-coloring of a graph is said to be proper if any adjacent edges are coloredwith different colors. An edge-colored graph is said to be properly edge-colored if its
edge-coloring is proper. For a graph G, ∆(G) denotes the maximum degree of G,and χ′ (G) denotes the edge chromatic number (chromatic index) of G, namely, theminimum positive integer k such that there exists a proper edge-coloring of G using
MSC2010: 05C05(Trees.), 05C15(Coloring of graphs and hypergraphs.), 05C70(Factorization,matching, partitioning, covering and packing).
∗Department of Information Science, Kochi University, Japan. kazuhiro@tutetuti.jp.

1

k colors. Note that ∆(G) ≤ χ′ (G) ≤ ∆(G) + 1 by Vizing’s theorem [4]. For an edgecolored graph (G, C, color), let Ec (G) denote the set of all the edges of G coloredwith c ∈ C, and let Gc := (V (G), Ec (G)). An edge-colored graph (G, C, color) is said
to be rainbow 1 if no two edges of G have the same color, that is, color(e) ̸= color(e′ )for any two distinct edges e and e′ of G.
Brualdi and Hollingsworth [1] conjectured the existence of n edge-disjoint rainbow spanning trees in some type of properly edge-colored complete graphs (Fig. 1).
Conjecture 1 (Brualdi and Hollingsworth [1]). Let (G, C, color) be an edge-coloredcomplete graph of order 2n (n ≥ 3). If each color induces a 1-factor of G, that is,Ec (G) is a perfect matching of G for any color c ∈ C, then G can be decomposed
into n edge-disjoint rainbow spanning trees.

Fig. 1: An example for n = 3 of the conjecture by Brualdi and Hollingsworth.
Kaneko et al. [2] conjectured a stronger statement than Conjecture 1 and proved
the existence of two edge-disjoint rainbow spanning trees.
Conjecture 2 (Kaneko, Kano, and Suzuki [2]). Every properly edge-colored complete graph of order n (n ≥ 5) has ⌊n/2⌋ edge-disjoint rainbow spanning trees.
Theorem 3 (Kaneko, Kano, and Suzuki [2]). Every properly edge-colored completegraph of order n (n ≥ 5) has two edge-disjoint rainbow spanning trees.
The term “rainbow” means that each color appears on at most one edge. Suzuki[3] generalized “one” to a mapping f from a given color set C to the set of nonnegative integers, and defined f -chromatic graphs as follows.
Definition 4 (Suzuki [3]). Let (G, C, color) be an edge-colored graph. Let f be amapping from C to the set of non-negative integers. Then (G, C, color) is said to bef -chromatic if |Ec (G)| ≤ f (c) for any color c ∈ C.
Suzuki [3] presented a necessary and sufficient condition for an edge-coloredgraph to have an f -chromatic spanning forest with exactly m components.
1A rainbow graph is also said to be heterochromatic, multicolored, totally multicolored, polychromatic, or colorful, and so on.

2In this paper, first, we prove the following theorem, which shows a relationshipbetween the existence of rainbow spanning trees and the existence of some type off -chromatic spanning trees.
Theorem 5. Let (G, C, color) be an edge-colored graph. Let f be a mapping definedas f (c) := χ′ (Gc ) for each color c ∈ C. Suppose that for any proper edge-coloringcolor′ with color set C ′ of G, the properly edge-colored graph (G, C ′ , color′ ) has k edgedisjoint rainbow spanning trees. Then, (G, C, color) has k edge-disjoint f -chromatic
spanning trees.
Proof. The outline of our proof is as follows. We recolor all the edges of G in sucha way that for each color c ∈ C, we properly color the edges of Gc with χ′ (Gc ) newcolors. Then, the recolored graph is properly edge-colored. By our assumption, therecolored graph has k edge-disjoint rainbow spanning trees. By restoring the colorsof the trees, we have k edge-disjoint f -chromatic spanning trees of (G, C, color).
More strictly, for each color c ∈ C, let (c, 1), (c, 2), . . . , (c, χ′ (Gc )) be new χ′ (Gc )colors, let Cc be the set of these colors, and let colorc be a proper edge-coloring ofSSGc with colors in Cc . Let C ′ := c∈C Cc and color′ := c∈C colorc . Then, color′ be thenew edge-coloring with color set C ′ of G such that color′ (e) = colorcolor(e) (e) for each
Tedge e of G. Since every coloring colorc is proper and c∈C Cc = ∅, the edge-coloredgraph (G, C ′ , color′ ) is a properly edge-colored.
By our assumption, (G, C ′ , color′ ) has k edge-disjoint rainbow spanning trees(Ti , C ′ , colori′ ) (i = 1, 2, . . . , k), where colori′ = {(e, color′ (e)) | e ∈ E(Ti )} ⊆ color′ .
For each (Ti , C ′ , colori′ ), we let colori := {(e, color(e)) | e ∈ E(Ti )} ⊆ color and we
consider the edge-colored tree (Ti , C, colori ). For any color c ∈ C, each (Ti , C ′ , colori′ )has at most |Cc | = χ′ (Gc ) edges whose color is (c, j) for some j ∈ {1, 2, . . . , χ′ (Gc )},since (Ti , C ′ , colori′ ) is rainbow. By the definition of color′ , color′ (e) = (c, j) for somej ∈ {1, 2, . . . , χ′ (Gc )} if and only if color(e) = c. Thus, (Ti , C, colori ) has at mostχ′ (Gc ) = f (c) edges whose color is c, which implies (Ti , C, colori ) is f -chromatic.
Therefore, G has k edge-disjoint f -chromatic spanning trees.
A properly edge-colored graph (G, C, color) is an edge-colored graph such that∆(Gc ) ≤ 1 for any color c ∈ C. To generalize this fact, we define an f -properlyedge-colored graph as follows.
Definition 6. Let f be a mapping from a color set C to the set of non-negativeintegers. An edge-colored graph (G, C, color) is said to be f -properly edge-coloredif ∆(Gc ) ≤ f (c) for any color c ∈ C. Then, the edge-coloring color is called anf -proper edge-coloring of G.
Given an edge-colored graph (G, C, color) and a mapping f from C to the set of
non-negative integers, we let f + (c) := f (c) + 1 for each color c ∈ C. We next prove
the following theorem by using Theorem 5 and Vizing’s theorem [4].
3Theorem 7. Let (G, C, color) be an f -properly edge-colored graph. Suppose that forany proper edge-coloring color′ with color set C ′ of G, the properly edge-colored graph(G, C ′ , color′ ) has k edge-disjoint rainbow spanning trees. Then, (G, C, color) has kedge-disjoint f + -chromatic spanning trees.
Proof. Let g be a mapping defined as g(c) := χ′ (Gc ) for each color c ∈ C. By Theorem 5, (G, C, color) has k edge-disjoint g-chromatic spanning trees T1 , T2 , . . . , Tk .
Since (G, C, color) is f -properly edge-colored, ∆(Gc ) ≤ f (c) for any color c ∈ C.
Thus, by Vizing’s theorem, g(c) = χ′ (Gc ) ≤ ∆(Gc ) + 1 ≤ f (c) + 1 ≤ f + (c) for eachcolor c ∈ C. Thus, a g-chromatic spanning tree of (G, C, color) is an f + -chromatic
spanning tree of (G, C, color). Hence, T1 , T2 , . . . , Tk are desired trees.
By using Conjecture 2, and Theorem 3, we have the following corollaries ofTheorem 7.
Corollary 8. If Conjecture 2 holds, then every f -properly edge-colored completegraph of order n (n ≥ 5) has ⌊n/2⌋ edge-disjoint f + -chromatic spanning trees.
Corollary 9. Every f -properly edge-colored complete graph of order n (n ≥ 5) has
two edge-disjoint f + -chromatic spanning trees.
We conclude this note with the following stronger conjecture, which claims theexistence of f -chromatic spanning trees instead of f + -chromatic spanning trees.
Conjecture 10. Every f -properly edge-colored complete graph of order n (n ≥ 5)has ⌊n/2⌋ edge-disjoint f -chromatic spanning trees.
Acknowledgments The author would like to thank the referees for carefully reading
the manuscript and providing valuable comments.

References[1] Brualdi, Richard A.; Hollingsworth, Susan; Multicolored Trees in Complete
Graphs. J. Combin. Theory Ser. B 68 (1996), 310–313.
[2] Kaneko, Atsushi; Kano, Mikio; Suzuki, Kazuhiro; Two Edge-Disjoint Heterochromatic Spanning Trees in Colored Complete Graphs. Matimyás Mat. 29(2006), 49–51.
[3] Suzuki, Kazuhiro; A Generalization of Heterochromatic Graphs and f Chromatic Spanning Forests. Graphs Combin. 29 (2013), 715–727.
[4] Vizing, V. G.; On an estimate of the chromatic class of a p-graph. Diskret. Analiz(1964), 25–30.
4