The rainbow arborescence conjecture posits that if the arcs of a directed graph with $n$ vertices are colored by $n-1$ colors such that each color class forms a spanning arborescence, then there is a spanning arborescence that contains exactly one arc of every color. We prove that the conjecture is true if the underlying undirected graph is a cycle.


翻译:彩虹树形图猜想提出:若一个有向图具有$n$个顶点,其弧被$n-1$种颜色着色,且每种颜色类均构成一棵生成树形图,则必存在一棵生成树形图,其恰好包含每种颜色的弧各一条。我们证明当该有向图对应的无向基础图为环时,该猜想成立。

0
下载
关闭预览

相关内容

图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
20+阅读 · 2020年2月14日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Arxiv
0+阅读 · 12月2日
VIP会员
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
20+阅读 · 2020年2月14日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员