New colored graphs towards a Brualdi-Hollingsworth conjecture

布鲁尔迪-霍林斯沃斯猜想的新彩色图表

• 批准号: 21740085
• 负责人: SUZUKI Kazuhiro
• 金额: $ 2.83万
• 依托单位: Kanagawa University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21740085/
• 关键词: 離散数学; グラフ理論; 全域木; 辺彩色; 辺着色; 異色全域木; f-異色グラフ; f-chromatic; BH予想; グラフ; graph

Brualdi et al. conjectured that a properly edge-colored complete graph of order 2n(>5)with 2n-1 colors can be decomposed into n edge-disjoint heterochromatic spanning trees. We generalized this conjecture by defining an f-chromatic graph, by which we can study stepwise the conjecture. In particular, we proved the generalized conjecture with f(c)=n-2. Moreover, we proved a necessary and sufficient condition for existence of an f-chromatic spanning forest with exactly w components, and generalized two previous results by applying the condition.

Brualdi等人证明了一个2n（>5）阶的2n-1种颜色的适当边着色完全图可以分解成n棵边不相交的异色生成树。我们通过定义一个f-色图来推广这个猜想，并利用它逐步研究这个猜想。特别地，我们证明了f（c）=n-2的广义猜想.此外，我们还证明了存在一个具有恰好w个分支的f-色生成森林的充要条件，并应用这个条件推广了两个已有的结果.