Given a graph $G$, the parameters $\chi(G)$ and $\omega(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(1) = 1$ and $f(x) \geq x$, for all $x \in \mathbb{N}$ is called a $\chi$-binding function for the given class of graphs $\cal{G}$ if every $G \in \cal{G}$ satisfies $\chi(G) \leq f(\omega(G))$, and the \emph{smallest $\chi$-binding function} $f^*$ for $\cal{G}$ is defined as $f^*(x) := \max\{\chi(G)\mid G\in {\cal G} \mbox{ and } \omega(G)=x\}$. In general, the problem of obtaining the smallest $\chi$-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of ($P_2+ P_3$, gem)-free graphs, and prove that the function $\phi:\mathbb{N}\rightarrow \mathbb{N}$ defined by $\phi(1)=1$, $\phi(2)=4$, $\phi(3)=6$ and $\phi(x)=\left\lceil\frac{1}{4}(5x-1)\right\rceil$, for $x\geq 4$ is the smallest $\chi$-binding function for the class of ($P_2+ P_3$, gem)-free graphs.


翻译:暂无翻译

0
下载
关闭预览

相关内容

牛津大学最新《计算代数拓扑》笔记书,107页pdf
专知会员服务
42+阅读 · 2022年2月17日
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 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日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
VIP会员
相关VIP内容
牛津大学最新《计算代数拓扑》笔记书,107页pdf
专知会员服务
42+阅读 · 2022年2月17日
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
143+阅读 · 2020年7月6日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 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日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员