本文選題：色數(shù)　切入點：誘導子樹　出處：《中國科學:數(shù)學》2017年05期 　論文類型：期刊論文

【摘要】：Gy餼rf餼s(1975)和Sumner(1981)分別獨立地提出了以下猜想:對于任意的樹T,存在一個函數(shù)f_T(x)使得每一個色數(shù)大于f_T(ω(G))的圖均包含T作為誘導子圖,其中ω(G)表示圖G的團數(shù).Gy餼rf餼s等(1980)證明了,若一個圖G不含三角形和長為4的圈,則G含有任一個χ(G)個頂點的樹作為誘導子圖.另外,他們還證明了,若G不含三角形,且χ(G)≥m+n,則G一定包含一個特殊的樹(m,n)-mop作為誘導子圖.本文推廣了Gy餼rf餼s等(1980)的這兩個結(jié)果,證明了(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.
【作者單位】： 南京師范大學數(shù)學科學學院;
【基金】：國家自然科學基金(批準號:11331003和11571180)資助項目
【分類號】：O157.5

【參考文獻】

相關(guān)期刊論文 前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 許怡安;張曉巖;;環(huán)面圖上的一個Lebesgue型定理及其在線性染色中的應用[J];中國科學:數(shù)學;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期

【共引文獻】

相關(guān)期刊論文 前7條

1 張瑩麗;許寶剛;;關(guān)于誘導子樹與圖的色數(shù)的一個注記[J];中國科學:數(shù)學;2017年05期

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

3 亢瑩利;王應前;;平面圖3色可染的一個充分條件[J];中國科學:數(shù)學;2013年04期

4 鞠平;;平面圖的線性著色[J];重慶工商大學學報(自然科學版);2013年02期

5 彩春麗;謝德政;;平面圖的線性著色[J];西南大學學報(自然科學版);2013年02期

6 彩春麗;謝德政;;平面圖3-可著色的3個充分條件[J];河南師范大學學報(自然科學版);2011年06期

7 許怡安;張曉巖;;環(huán)面圖上的一個Lebesgue型定理及其在線性染色中的應用[J];中國科學:數(shù)學;2011年05期

【二級參考文獻】

相關(guān)期刊論文 前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輯:數(shù)學);2008年12期

6 侯建鋒;吳建良;劉桂真;劉彬;;平面圖和系列平行圖的無圈邊染色[J];中國科學(A輯:數(shù)學);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期

【相似文獻】

相關(guān)期刊論文 前2條

1 陳治柏;與圖的中心有關(guān)的兩個定理[J];新疆大學學報(自然科學版);1983年03期

2 ;[J];;年期

相關(guān)碩士學位論文 前3條

1 周成;圖的距離拉普拉斯譜與距離無符號拉普拉斯譜[D];東南大學;2016年

2 蔣林承;圖數(shù)據(jù)管理中最小唯一誘導子圖查詢研究[D];國防科學技術(shù)大學;2014年

3 林冰凱;k邊誘導子圖問題的參數(shù)復雜性[D];上海交通大學;2013年

，

本文編號：1602714