(g, f)-Chromatic spanning trees and forests
(g, f)-Chromatic spanning trees and forests
复制标题
DOI：
--
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Kazuhiro Suzuki
中科院分区：
文献类型：
--
作者：
Kazuhiro Suzuki
异色(或彩虹)图是边具有不同颜色的边色图，也就是说，每种颜色最多出现一次。在本文中，我提出了一个$(g，f)$-色图作为一个边色图，其中每个颜色$c$至少出现$g(C)$次，至多出现$f(C)$次。给出了边色图有$(g，f)$-色生成树的充要条件(不一定是真的)。利用这个准则，我证明了边色完全图$G$有一棵生成树，其颜色概率分布与$G$的颜色概率分布“相似”。此外，我猜想一个阶为$2n$$(n\ge3)$的边色完全图$G$可以被分成$n$个边不相交的生成树，使得每个生成树的颜色概率分布与$G$的颜色概率分布“相似”。
A heterochromatic (or rainbow) graph is an edge-colored graph whose edges have distinct colors, that is, where each color appears at most once. In this paper, I propose a $(g,f)$-chromatic graph as an edge-colored graph where each color $c$ appears at least $g(c)$ times and at most $f(c)$ times. I also present a necessary and sufficient condition for edge-colored graphs (not necessary to be proper) to have a $(g,f)$-chromatic spanning tree. Using this criterion, I show that an edge-colored complete graph $G$ has a spanning tree with a color probability distribution `similar' to that of $G$. Moreover, I conjecture that an edge-colored complete graph $G$ of order $2n$ $(n \ge 3)$ can be partitioned into $n$ edge-disjoint spanning trees such that each has a color probability distribution `similar' to that of $G$.