This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.


翻译:本文研究了正确行走连接号的问题: 给一个未定向连接的图形, 我们的目标是用尽可能少的颜色来颜色它的边缘, 这样在图形的每对顶端之间就存在一种适当的彩色行走, 也就是说, 行走不使用同一颜色的连续两边。 问题已经在几类图表中解决, 但一般情况下还是开放的。 我们确认, 问题总是可以在图形大小的多元时间里解决, 我们提供图表的定性, 每一个可能的值都与$k$的颜色适当连接 。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
8+阅读 · 2020年5月2日
Arxiv
101+阅读 · 2020年3月4日
Self-Attention Graph Pooling
Arxiv
5+阅读 · 2019年4月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
相关论文
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
8+阅读 · 2020年5月2日
Arxiv
101+阅读 · 2020年3月4日
Self-Attention Graph Pooling
Arxiv
5+阅读 · 2019年4月17日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员