The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number. This work takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. We here pursue this line of research, but with taking Zaslavsky's colourings as our notion of proper colourings. We study the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects.


翻译:染色体数是指正确显示图表顶部所需的最低颜色数量, 指正确显示图表顶部所需的最起码颜色数量, 是图彩色理论中最核心的概念之一。 文献中已经调查了其中几个值得关注的方面, 包括修改适当颜色的变异。 这些变异包括, 特别是, 图表的色色数, 也就是正确显示图表顶端所需的最大颜色数量, 以便在某些边缘排列每个可能的不同颜色组合。 这个参数的行为引出了许多感兴趣的调查, 揭示了与染色体数字的相似性和差异。 这项工作是在近期的趋势中进行的, 目的是将图表的染色学理论扩展至已签名的颜色范围, 特别是研究经典结果如何适应已签名的颜色。 该行迄今为止完成的大部分工作涉及两个关于已签名的图表的正确颜色数字的简单化分析, 归因于Zaslavsky 和 Guenin 。 将我们标定的颜色操作的直系背景数概括到签名的颜色分析结果, 最近由Lajjoch 开始, 我们的颜色直系开始, 与我们标定的颜色的颜色的常规研究结果相关。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
【知识图谱@ACL2020】Knowledge Graphs in Natural Language Processing
专知会员服务
65+阅读 · 2020年7月12日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月19日
Arxiv
0+阅读 · 2021年11月18日
Arxiv
0+阅读 · 2021年11月17日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
Arxiv
6+阅读 · 2018年11月29日
Arxiv
23+阅读 · 2018年10月1日
Arxiv
4+阅读 · 2018年5月21日
Arxiv
7+阅读 · 2018年3月21日
VIP会员
相关VIP内容
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
【知识图谱@ACL2020】Knowledge Graphs in Natural Language Processing
专知会员服务
65+阅读 · 2020年7月12日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【干货书】真实机器学习,264页pdf,Real-World Machine Learning
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年11月19日
Arxiv
0+阅读 · 2021年11月18日
Arxiv
0+阅读 · 2021年11月17日
Signed Graph Attention Networks
Arxiv
7+阅读 · 2019年9月5日
Arxiv
6+阅读 · 2018年11月29日
Arxiv
23+阅读 · 2018年10月1日
Arxiv
4+阅读 · 2018年5月21日
Arxiv
7+阅读 · 2018年3月21日
Top
微信扫码咨询专知VIP会员