k色图的连通性

徐述; 欧阳剑新; 石胜坤

您当前的位置：

首页 >

文章列表页 >

k色图的连通性

应用基础研究 | 更新时间：2026-09-14

- k色图的连通性
- The Connectivity of k-Chromatic Graphs
- 中北大学学报（自然科学版） 2008年第2期页码：101-104
- 作者机构：
  
  1. 中国人民解放军信息工程大学电子技术学院
  2. 微联国际软件公司
  3. 北京大学数学科学学院
- 作者简介：
- 基金信息：
- DOI：
  中图分类号：
- 纸质出版：2008
- 稿件说明：
移动端阅览
徐述, 欧阳剑新, 石胜坤. k色图的连通性[J]. 中北大学学报（自然科学版）, 2008,(2):101-104.

徐述, 欧阳剑新, 石胜坤. The Connectivity of k-Chromatic Graphs[J]. 2008, (2): 101-104.
徐述, 欧阳剑新, 石胜坤. k色图的连通性[J]. 中北大学学报（自然科学版）, 2008,(2):101-104. DOI：

徐述, 欧阳剑新, 石胜坤. The Connectivity of k-Chromatic Graphs[J]. 2008, (2): 101-104. DOI：

摘要

研究和讨论了图的顶点着色问题中k色图的连通性

利用归纳与迭代的方法证明了对于任何k色连通图G

存在顶点V(G)的一个着色X1

…

使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen

Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.

Abstract

The connectivity of k-chromatic graphs were discussed.By induction and iteration

it was proved that for any connected k-chromatic graph G

there exists a k coloring X1

…

Xk of V(G) such that Gk(Xi) is connected for each i.Thus the conjecture of Chen

Schelp and Shreve was verified.Finally the conclusion was further generalized.

关键词

Keywords

references

Nelson R,Wilson R J.Graph Colourings[M].London:Pitman Research Notes in Mathematic Series,1990.

Jensen T R,Toft B.Graph Coloring Problems[M].New York:Wiley-Interscience,1995.

Bondy J A,Murty U S R.Graph Theory with Applications[M].London:Macmillan,1976.

Chen G T,Schelp R H,Shreve W E.A special k-coloring for a connected k-chromatic graph[J].Discrete Mathe-matics,1997,170(1-3):231-236.

Szigeti J,Tuza Z.Generalized colorings and avoidable orientations[J].Discuss.Math.Graph Theory,1997,17:137-145.

Kawarabayashi K I,Lee O,Yu X X.Non-separating paths in 4-connected graphs[J].Annals of Combinatorics,2005,9(1):47-56.

Kawarabayashi K,Luo R,Niu J B,et al.On the structure of k-connected graphs without K-k-minor[J].EuropeanJournal of Combinatorics,2005,26(3-4):293-308.

Huang X L,Jin Z M,Yu X X,et al.Contractible cliques in k-connected graphs[J].Graphs and Combinatorics,2006,22(3):361-370.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

茶叶生物炭磁性材料对水中重金属铬的超声吸附研究

基于Transformer⁃FPGA协同特征建模的光电坐标高精度定位技术

基于低分子质量PEI的类PEG聚合物基因载体

面向高空爆炸试验的冲击波测试系统

OFDM中基于DFT的自适应信道估计算法