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

点关联较少3-面的平面图的全染色 被引量：1

The total coloring of planar graphs with a few 3-faces incidents with vertex
下载PDF
导出
摘要 证明了对每点至多关联2个3-面的平面图,全染色猜想成立.对每点至多关联2个3-面且Δ(G)≥8的平面图,有xT(G)=Δ(G)+1.对每点至多关联(Δ(G)/2)个3-面且Δ(G)≥9的平面图,有xT(G)=Δ(G)+1. It is proved that for a planar graph G which every vertex is incident with at most two 3-faces, the total coloring conjecture is true. Moreover, the total chromatic number of G is △（G） ＋ 1 if △（G） ≥8. The total chromatic number of a planar graph G is A（G） ＋ 1 if △（G） ≥9 and every vertex is incident with at most △＂（ G）/2＂3-faces.
作者 孙向勇
机构地区 山东经济学院统计与数学学院
出处 《山东大学学报（理学版）》 CAS CSCD 北大核心 2007年第5期14-18,共5页 Journal of Shandong University(Natural Science)
关键词 平面图 全染色 全染色数 planar graph total coloring total chromatic number
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献16

  • 1邦迪JA 默蒂USR.图论及其应用[M].北京:科学出版社,1984..
  • 2Behzad M.Graphs and their chromatic numbers[D].Michigan State University,1965.
  • 3Vizing V G.On an estimate of the chromatic class of a p-graph (in Russian)[J].Metody Diskret Analiz,1964,3:25-30.
  • 4Rosenfeld M.On the total coloring of certain graphs[J].Israel Math,1971,9:396-402.
  • 5Vijayaditya N.On total chromatic number of a graph[J].London Math Soc,1971,3(2):405-408.
  • 6Kostochka A V.The total coloring of a multigraph with maximal degree 4[J].Discret Math,1977,17:161-163.
  • 7Kostochka A V.The total chromatic number of any multigraph with maximum degree five is at most seven[J].Discret Math,1996,162:199-214.
  • 8Borodin O V.On the total coloring of planar graphs[J].Reine Angew Math,1989,394:180-185.
  • 9Yap H P.Total colourings of graphs,Lecture notes in mamthematics,1623[M].Berlin:Springer,1996.
  • 10Sanders D P,Zhao Y.On total 9-coloring planar graphs of maximum degree seven[J].J Graph Theory,1999,31:67-73.

二级参考文献9

  • 1[1]邦迪 J A,默蒂 U S R.图论及其应用[M].吴望名译.北京:科学出版社,1984.
  • 2[2]Jensen T R,Toft B.Graph coloring problems[M].New York:John and Wiley & Sons,1995.
  • 3[3]Sanchez-Arroyo A.Determining the total coloring number is NP-hard[J].Discrete Math,1989,78(3):315-319.
  • 4[4]Borodin O V,Kostochka A V,Woodall D R.Total colorings of planar graphs with large maximum degree[J].Graph Theory,1997,26(1):53-59.
  • 5[5]Daniel P S,Zhao Y.On total 9-coloring planar graphs of maximum degree seven[J].Graph Theory,1999,31(1):67-73.
  • 6[6]Wang P,Wu J L.A note on total colorings of planar graph without 4-cycles[J].Discussiones Mathematicae Graph Theory,2004,24(1):125-135.
  • 7[7]Gross J L,Tucker T W.Topological graph theory[M].New York:John and Wiley & Sons,1987.
  • 8[8]Borodin O V.On the total coloring of planar graphs[J].Reine Angew.Math.1989,394(2):180-185.
  • 9[9]Borodin O V,A V Kostochka,Woodall D R.List edge and list total colorings of multigraphs[J].Combin.Theory (B),1997,71(1):184-204.

共引文献41

同被引文献15

  • 1孙向勇.关于3-圈不重点的平面图全染色的一个结论[J].山东建筑大学学报,2006,21(4):374-376. 被引量：4
  • 2孙向勇.特殊平面图的全染色[J].山东师范大学学报（自然科学版）,2007,22(1):10-12. 被引量：3
  • 3[1]邦迪 J A,默蒂 U S R.图论及其应用[M].吴望名译.北京:科学出版社,1984.
  • 4[2]Behzad M.Graphs and their chromatic numbers[D].Michigan:Michigan State University,1965.
  • 5[3]Vizing V G.On an estimate of the chromatic class of a p-graph (in Russian)[J].Metody Diskret Analiz,1964(3):25-30.
  • 6[4]Rosenfeld M.On the total coloring of certain graphs[J].Israel Math,1971(9):396-402.
  • 7[5]Vijayaditya N.On total chromatic number of a graph[J].London Math Soc,1971,3(2):405-408.
  • 8[6]Kostochka A V.The total coloring of a multigraph with maximal degree 4[J].Discrete Math,1977,17:161-163.
  • 9[7]Kostochka A V.The total chromatic number of any multigraph with maximum degree five is at most seven[J].Discrete Math,1996,162:199-214.
  • 10[8]Borodin O V.On the total coloring of planar graphs[J].Reine Angew Math,1989,394:180-185.

引证文献1

二级引证文献1

山东大学学报（理学版）
2007年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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