期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

不含HVN和C_4为导出子图的图的色数 被引量：2

The Chromatic Number of {HVN,C_4}-free Graphs
下载PDF
导出
摘要 以强完美图定理为基础,通过对不含HVN(即P3+2K2)和C4为导出子图的图的结构进行分析,得到了该类图色数的关于团数线性函数表达式的上界. By the strong perfect graph theorem, the structural characterization of { HVN,C4}- free graphs is analyzed, and the upper bound on chromatic number of { HVN, C4 } - free graphs with linear function in term of clique number is obtained.
作者 王晓 张东翰
机构地区 商洛学院数学与计算机应用学院
出处 《河南科学》 2015年第3期333-335,共3页 Henan Science
基金 陕西省教育厅自然科学专项基金资助项目(12JK0889) 商洛学院科研基金(09SKY005 14SKY003)
关键词 色数 导出子图 团数 chromatic number induced subgraph clique number
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献9

  • 1Reinhard D. Graph theory[M]. 2nd ed. HongKong: Springer-Verlag, 2000.
  • 2Erdos P. Graph theory and probability[J]. Canad J Math, 1959, 11 ( 1 ) : 34-38.
  • 3Chudnovsky M, Robertson N, Seymour P. The strong perfect graph theorem l-J ]. Annals of Mathematics, 2006, 164 ( 1 ) : 51-229.
  • 4宋春伟.强完美图定理及相关的问题[J].数学进展,2008,37(2):153-162. 被引量：8
  • 5Gyrrfrs A. Problems from the world surrounding perfect graphs[J]. Zastow Math, 1987, 19(4):413-441.
  • 6Wagon S. A bound on the chromatic number of graphs without certain induced subgraphs[J]. Journal of Combin Theory Series B, 1980, 29(3) : 345-346.
  • 7Hoang C T, McDiarmid C. On the divisibility of graphs[J]. Discrete Math, 2002, 242( 1 ) : 145-156.
  • 8Randerath B, Schiermeyer I. Vertex coloring and forbidden subgraphs-a survey[J]. Graphs Combin, 2004, 20( 1 ) : 1-40.
  • 9段芳,张维娟.不含2K_1+K_2和C_4作为导出子图的图的色数(英文)[J].华东师范大学学报（自然科学版）,2014(1):9-12. 被引量：5

二级参考文献49

  • 1Berge, C., Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin- Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 1961, 10: 114-115.
  • 2Berge, C., Perfect graphs, Six Papers on Graph Theory: 1-21, Calcutta: Indian Statistical Institute, 1963.
  • 3Berge, C., Some classes of perfect graphs, Graph Theory and Theoretical Physics, 155-165, Academic Press, London, 1967.
  • 4Berge, C., Principes de Combinatoire, Dunod, Paris, 1968.
  • 5Berge, C. and Chvatal, V., Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, Annals of Discrete Mathematics, 21, North-Holland Publishing Co., Amsterdam, 1984.
  • 6Berge, C. and Ramlrez Alfonsln, J. L., Origins and Genesis, Perfect Graphs, Wiley-Intersci. Ser. Discrete Math. Optim., 1-12, Wiley, Chichester, 2001.
  • 7Berge, C., Introduction a. la Theorie des Hypergraphes, Les Presses de l'Universite de Montreal, Montreal,Que., 1973, Seminaire de Mathematiques Superieures, No. 51 (Ete 1971).
  • 8Berge, C., Graphs and Hypergraphs, North-Holland Publishing Co., Amsterdam, revised, edition, 1976, Translated from the French by Edward Minieka, North-Holland Mathematical Library, Vol. 6.
  • 9Chudnovsky, M., Berge Trigraphs and Their Applications, PhD Thesis, Princeton University, 2003.
  • 10Chudnovsky, M., Perfect graphs, Available at www.aimath.org/pastworkshops/perfectgraph.html

共引文献9

同被引文献25

  • 1Reinhard D.Graph theory[M].2nd ed.Hong Kong,China:Springer-Verlag,2000.
  • 2Erdos P.Graph theory and probability[J].Canad J Math,1959,11:34-38.
  • 3Reed B.ω,Δandχ[J].Journal of Graph Theory,1998,374:177-212.
  • 4Chudnovsky M,Robertson N,Seymour P.The strong perfect graph theorem[J].Annals of Mathematics,2006,164:51-229.
  • 5Gyárfás A.Problems from the world surrounding perfect graphs[J].Zastow Mat,1987,19:413-441.
  • 6Wagon S.A bound on the chromatic number of graphs without certain induced subgraphs[J].Journal of Combin Theory:Series B,1980,29:345-346.
  • 7Hoang C T,Mc Diarmid C.On the divisibility of graphs[J].Discrete Math,2002,242:145-156.
  • 8Fan G,Xu B,Ye T,et al.Forbidden subgraphs and 3-coloring[J].Siam J Disc Math,2014,28:1226-1256.
  • 9Randerath B,Schiermeyer I.A note on brooks theorem for triangle-free graphs[J].Australas J Comb,2002,26:3-9.
  • 10Randerath B,Schiermeyer I.Vertex coloring and forbidden subgraphs—a survey[J].Graphs Combin,2004,20:1-40.

引证文献2

河南科学
2015年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部