The Connectivity of k-Chromatic Graphs

徐述; 欧阳剑新; 石胜坤

您当前的位置：

首页 >

文章列表页 >

The Connectivity of k-Chromatic Graphs

更新时间：2026-09-14

- The Connectivity of k-Chromatic Graphs
- k色图的连通性
- Issue 2, Pages: 101-104(2008)
- 作者机构：
  
  1. 中国人民解放军信息工程大学电子技术学院
  2. 微联国际软件公司
  3. 北京大学数学科学学院
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2008
- 稿件说明：
移动端阅览
徐述, 欧阳剑新, 石胜坤. The Connectivity of k-Chromatic Graphs[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Configuration Design and Research of a Hybrid Quadruped Perilla Sowing Robot

High⁃Precision Photoeletric Coordinate Positioning Technology Based on Transformer⁃FPGA Collaborative Feature Modeling

Study on the Removal of CO2 in Confined Space by High⁃Gravity Enhanced Potassium Hydroxide Coupled Potassium Glycinate Solution

Adaptive DFT Channel Estimation Algorithm Based on Joint Delay and SNR Estimation in OFDM System

Design of Parallel Robot Experimental Platform Based on Reconfigurable Innovative Components

Related Author

No data

Related Institution

No data

⁰