A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests |
| |
Authors: | Kazuhiro Suzuki |
| |
Institution: | 1. Department of Information Science, Kochi University, Kochi, 780-8520, Japan
|
| |
Abstract: | 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 ${|E(G)| > \binom{n-m}{2}}$ has an f-chromatic spanning forest with exactly m (1 ≤ m ≤ n ? 1) components if ${g(c) \le \frac{|E(G)|}{n-m}f(c)}$ for any color c. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|