Mathematics – Combinatorics
Scientific paper
2011-06-13
Mathematics
Combinatorics
8 pages, 3 figures
Scientific paper
In 2001, Brualdi and Hollingsworth proved that an edge-colored balanced complete bipartite graph Kn,n with a color set C = {1,2,3,..., 2n-1} has a heterochromatic spanning tree if the number of edges colored with colors in R is more than |R|^2 /4 for any non-empty subset R \subseteq C, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors, namely, any color appears at most once. In 2010, Suzuki generalized heterochromatic graphs to f-chromatic graphs, where any color c appears at most f(c). Moreover, he presented a necessary and sufficient condition for graphs to have an f-chromatic spanning forest with exactly w components. In this paper, using this necessary and sufficient condition, we generalize the Brualdi-Hollingsworth theorem above.
No associations
LandOfFree
An f-chromatic spanning forest of edge-colored complete bipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An f-chromatic spanning forest of edge-colored complete bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An f-chromatic spanning forest of edge-colored complete bipartite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-429511