关于诱导子树与图的色数的一个注记

发布时间：2018-03-12 18:14

  本文选题：色数　切入点：诱导子树　出处：《中国科学:数学》2017年05期 　论文类型：期刊论文

【摘要】：Gy饩rf饩s(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gy饩rf饩s等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gy饩rf饩s等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)m(k+1)+n,其中T为(m,n)-mop.
[Abstract]:The following conjectures were put forward independently by Gy, RF, 1975) and Sumners1981respectively: for any tree T, there exists a function f T T x) such that each graph with a chromatic number greater than fStut T (蠅 T) contains T as an inductor graph. It is proved that if a graph G does not contain a triangle and a cycle of 4, then G contains a tree with any vertex of 蠂 ~ 2 G as an induced subgraph. In addition, they prove that if G does not contain a triangle, In this paper, we generalize the two results of Gy + RF + s and prove that 1) if any vertex of G contains at most k triangles and l cycles with length 4, If the vertices of G are at most contained in k triangles and can not be induced by T, then 蠂 ~ + G ~ (m ~ (1)) n, where T is a mnn-mop-mop-mop-mp, is found to be a tree with any t points as an inductive subgraph (2) if the vertex of G is at most contained in k triangles and can not be induced to T, then 蠂 ~ + G ~ (2) K ~ (?) k ~ (1) n.
【作者单位】： 南京师范大学数学科学学院;
【基金】：国家自然科学基金(批准号:11331003和11571180)资助项目
【分类号】：O157.5

【参考文献】

相关期刊论文 前5条

1 WAN Min;XU BaoGang;;Acyclic edge coloring of planar graphs without adjacent cycles[J];Science China(Mathematics);2014年02期

2 ;Acyclic edge coloring of graphs with large girths[J];Science China(Mathematics);2012年12期

3 许怡安;张晓岩;;环面图上的一个Lebesgue型定理及其在线性染色中的应用[J];中国科学:数学;2011年05期

4 ;Improved bounds on linear coloring of plane graphs[J];Science China(Mathematics);2010年07期

5 ;On 3-colorability of planar graphs without adjacent short cycles[J];Science China(Mathematics);2010年04期

【共引文献】

相关期刊论文 前7条

1 张莹丽;许宝刚;;关于诱导子树与图的色数的一个注记[J];中国科学:数学;2017年05期

2 LIU MuHuo;XU BaoGang;;Bipartition of graph under degree constraints[J];Science China(Mathematics);2015年04期

3 亢莹利;王应前;;平面图3色可染的一个充分条件[J];中国科学:数学;2013年04期

4 鞠平;;平面图的线性着色[J];重庆工商大学学报(自然科学版);2013年02期

5 彩春丽;谢德政;;平面图的线性着色[J];西南大学学报(自然科学版);2013年02期

6 彩春丽;谢德政;;平面图3-可着色的3个充分条件[J];河南师范大学学报(自然科学版);2011年06期

7 许怡安;张晓岩;;环面图上的一个Lebesgue型定理及其在线性染色中的应用[J];中国科学:数学;2011年05期

【二级参考文献】

相关期刊论文 前9条

1 ;Total coloring of embedded graphs of maximum degree at least ten[J];Science China(Mathematics);2010年08期

2 ;Improved bounds on linear coloring of plane graphs[J];Science China(Mathematics);2010年07期

3 ;Linear coloring of graphs embeddable in a surface of nonnegative characteristic[J];Science in China(Series A:Mathematics);2009年05期

4 ;Acyclic edge colorings of planar graphs and series-parallel graphs[J];Science in China(Series A:Mathematics);2009年03期

5 王维凡;李超;;非负特征图的线性染色[J];中国科学(A辑:数学);2008年12期

6 侯建锋;吴建良;刘桂真;刘彬;;平面图和系列平行图的无圈边染色[J];中国科学(A辑:数学);2008年12期

7 ;On the adjacent-vertex-strongly-distinguishing total coloring of graphs[J];Science in China(Series A:Mathematics);2008年03期

8 ;On adjacent-vertex-distinguishing total coloring of graphs[J];Science in China,Ser.A;2005年03期

9 ;The Entire Coloring of Series-Parallel Graphs[J];Acta Mathematicae Applicatae Sinica(English Series);2005年01期

【相似文献】

相关期刊论文 前2条

1 陈治柏;与图的中心有关的两个定理[J];新疆大学学报(自然科学版);1983年03期

2 ;[J];;年期

相关硕士学位论文 前3条

1 周成;图的距离拉普拉斯谱与距离无符号拉普拉斯谱[D];东南大学;2016年

2 蒋林承;图数据管理中最小唯一诱导子图查询研究[D];国防科学技术大学;2014年

3 林冰凯;k边诱导子图问题的参数复杂性[D];上海交通大学;2013年

，

本文编号：1602714