An $(n,m)$-graph is a graph with $n$ types of arcs and $m$ types of edges. A homomorphism of an $(n,m)$-graph $G$ to another $(n,m)$-graph $H$ is a vertex mapping that preserves adjacency, its direction, and its type. The minimum value of $|V(H)|$ such that $G$ admits a homomorphism to $H$ is the $(n,m)$-chromatic number of $G$, denoted by $\mychi_{n,m}(G)$. This parameter was introduced by Ne\v{s}et\v{r}il and Raspaud (J. Comb. Theory. Ser. B 2000). In this article, we show that the arboricity of $G$ is bounded by a function of $\mychi_{n,m}(G)$, but not the other way round. We also show that acyclic chromatic number of $G$ is bounded by a function of $\mychi_{n,m}(G)$, while the other way round bound was known beforehand. Moreover, we show that $(n,m)$-chromatic number for the family of graphs having maximum average degree less than $2+ \frac{2}{4(2n+m)-1}$, which contains the family of planar graphs having girth at least $8(2n+m)$ as a subfamily, is equal to $2(2n+m)+1$. This improves the previously known result which proved that the $(n,m)$-chromatic number for the family planar graphs having girth at least $10(2n+m)-4$ is equal to $2(2n+m)+1$. It is known that the $(n,m)$-chromatic number for the family of partial $2$-trees bounded below and above by quadratic functions of $(2n+m)$ and that the lower bound is tight when $(2n+m)=2$. We show that the lower bound is not tight when $(2n+m)=3$ by improving the corresponding lower bounds by one. We manage to improve some of the upper bounds in these cases as well.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【2022新书】数据科学的实用线性代数,328页pdf
专知会员服务
135+阅读 · 2022年9月17日
牛津大学最新《计算代数拓扑》笔记书,107页pdf
专知会员服务
42+阅读 · 2022年2月17日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
39+阅读 · 2020年8月22日
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
概率图模型体系:HMM、MEMM、CRF
机器学习研究会
30+阅读 · 2018年2月10日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
VIP会员
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
概率图模型体系:HMM、MEMM、CRF
机器学习研究会
30+阅读 · 2018年2月10日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员