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.

布鲁阿尔迪等人。推测具有 2n-1 种颜色的 2n(>5) 阶的正确边着色完全图可以分解为 n 个边不相交的异色生成树。我们通过定义一个f色图来推广这个猜想，通过它我们可以逐步研究这个猜想。特别地，我们证明了 f(c)=n-2 的广义猜想。此外，我们证明了存在具有恰好w个分量的f色生成森林的充要条件，并应用该条件推广了先前的两个结果。