A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests

作者：Suzuki Kazuhiro^*

来源：Graphs and Combinatorics, 2013, 29(3): 715-727.

DOI：10.1007/s00373-011-1125-z

• f-Chromatic
• Heterochromatic
• Rainbow
• Multicolored
• Totally multicolored
• Polychromatic
• Colorful
• Edge-coloring
• k-bounded coloring
• Spanning tree
• Spanning forest

In 2006, Suzuki, and Akbari and Alipour independently presented a necessary and sufficient condition for edge-colored graphs to have a heterochromatic spanning tree, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors. In this paper, we propose f-chromatic graphs as a generalization of heterochromatic graphs. An edge-colored graph is f-chromatic if each color c appears on at most f(c) edges. We also present a necessary and sufficient condition for edge-colored graphs to have an f-chromatic spanning forest with exactly m components. Moreover, using this criterion, we show that a g-chromatic graph G of order n with has an f-chromatic spanning forest with exactly m (1 a parts per thousand currency sign m a parts per thousand currency sign n - 1) components if for any color c.

• 出版日期2013-5