禁用诱导子图与图的染色数关系研究

Gyárfás has introduced the concept of $\chi(G)$-bound functions thereby extending the notion of perfectness. Here, a family F of graphs G is called $\chi$-bound with $\chi$-binding function f, if $\chi(H)\leq f(\omega(H))$ holds whenever H is an induced subgraph of G in F. There are series of papers on topic of choosing forbidden induced subgraphs guarantee that a family of graphs is $\chi$-bound. A $B(m,n)$ is defined by identifying one end vertex of a path of m vertices with the center of a star $K_{1,n}$, if identifying both of the end vertices, denote it by $DB(m,n)$. This project is focus on the following questions: 1. Does there exists a $\chi$-binding function $f$ for the graphs forbidden the induced subgraph $B(m,n)$? 2. Does there exists a $\chi$-binding function $f$ for the graphs forbidden the induced subgraph $DB(m,n)$? 3. For each tree T with radius three, forbidden the induced subgraph T, is G $\chi$-bounded?

Gyárfás 于1987年对完美图概念作了一个推广:对于图$G$,如果存在函数$f$使得任意诱导子图$H\subseteq G$,都有$\chi(H)\leq f(\omega(H))$,则称图G是$\chi$-有界的,函数$f$称为$\chi$-限定函数.有很多文章讨论禁用合适的诱导子图使得图是$\chi$-有界的.令$B(m,n)$表示将$m$长路的一个端点和星图$k_{1,n}$的中心捏合在一起的图.将路的两端都捏合一个$k_{1,n}$,记作$DB(m,n)$. 本项目主要考虑以下问题:1.若图$G$不含$B(m,n)$作为诱导子图,那么$G$是否是$\chi$-有界的?2.若图$G$不含$DB(m,n)$作为诱导子图,那么$G$是否是$\chi$-有界的? 3.任意半径为3的树$T$,若图$G$不含$T$作为诱导子图,那么图$G$是否存在$\chi$-限定函数$f$.

Gyárfás于 1987 年对完美图概念作了一个推广:对于图 $G$，如果存在函数$f$使得任意诱导子图$H\subseteq G$，都有 $\chi(H)\leq f(\omega(H))$, 则称图G是$\chi$-有界的,函数$f$称为$\chi$-限定函数。有很多文章讨论禁用合适的诱导子图使得图是$\chi$-有界的。本项目研究中，我们主要研究了三类染色数上界问题：第一类，我们考虑染色数上界函数只和团数相关的问题；我们证明了对以两类特殊的半径大于3的树( DB(6, k) 和 DB(7, k)) 为禁用诱导子图图 $G$ 而言，其染色数上界函数是可以只和团数相关，是$\chi$-有界。第二类，禁用了一些诱导圈，我们考虑染色数上界是与团数及最大度同时相关的问题即 Reed 猜想问题；我们证明了无三圈且 even-hole-free 的图的染色数上界就是Reed界，同时我们也证明了对围长大于4的even-hole-free图而言，其染色数也是满足Reed猜想的。第三类，我们考虑了一种强边染色上界问题，我们通过对局部结构的重新排序，将已有的结果提升了一个最大度。