A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests. Graphs and Combinatorics
A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests. Graphs and Combinatorics
复制标题
异色图和 f 色跨越森林的推广。
DOI：
10.1007/s00373-011-1125-z
复制
发表时间：
2013
影响因子：
0.7
通讯作者：
Kazuhiro
中科院分区：
文献类型：
--
作者：
Suzuki;Kazuhiro
在2006年，Suzuki，Akbari和Alipour独立地给出了边着色图有异色生成树的一个充要条件，其中异色生成树是边具有不同颜色的生成树。在本文中，我们提出f-色图作为异色图的推广。一个边着色图是f-着色的，如果每种颜色在至多f（c）条边上着色.我们还给出了边着色图存在正合分支的全色生成森林的一个充要条件。利用这一准则，我们证明了n阶的g-色图G存在正合m（1 ≤m≤n− 1）个分支的全色生成林，如果对任意色c.
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 proposef-chromaticgraphs as a generalization of heterochromatic graphs. An edge-colored graph isf-chromaticif each colorcappears on at mostf(c) edges. We also present a necessary and sufficient condition for edge-colored graphs to have anf-chromatic spanning forest with exactlymcomponents. Moreover, using this criterion, we show that ag-chromatic graphGof ordernwithhas anf-chromatic spanning forest with exactlym(1 ≤m≤n− 1) components iffor any colorc.