无割边三正则图三边着色的一个充分必要条件(英文)

翟绍辉; 冯永锝

您当前的位置：

首页 >

文章列表页 >

无割边三正则图三边着色的一个充分必要条件(英文)

更新时间：2026-01-21

- 无割边三正则图三边着色的一个充分必要条件(英文)
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Issue 3, (2003)
- 作者机构：
  
  新疆大学数学与系统科学学院,新疆大学数学与系统科学学院新疆乌鲁木齐830046,新疆,乌鲁木齐,830046
- 作者简介：
- 基金信息：
- DOI：
  CLC： O157.5
- Published：2003
- 稿件说明：
移动端阅览
[1]翟绍辉,冯永锝.无割边三正则图三边着色的一个充分必要条件(英文)[J].新疆大学学报(自然科学版),2003(03):233-235.

翟绍辉, 冯永锝. 无割边三正则图三边着色的一个充分必要条件(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2003, (3).
[1]翟绍辉,冯永锝.无割边三正则图三边着色的一个充分必要条件(英文)[J].新疆大学学报(自然科学版),2003(03):233-235. DOI：

翟绍辉, 冯永锝. 无割边三正则图三边着色的一个充分必要条件(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2003, (3). DOI：

摘要

设G是无割边三正则图

θ={C1

…

Ck}是G一个圈覆盖

定义一新图G(θ)=(V

这里V={C1

…

Ck}

(Ci

Cj)∈E当且仅当E(Ci)∩E(Cj)≠ (1≤i≠j≤k).那么G是三边着色的充分必要条件是G有一个圈的一或二次覆盖θ并且G(θ)是二或三点着色.这个结论给出了一个判定无割边三正则图是三边着色的方法.

Abstract

Let \$G\$ be a bridgeless cubic graph and \$θ=｛C\-1

C\-2

…

C\-K｝\$ be a cycle cover of G.Define a new graph \$G(θ)=(V

\$ where \$V=｛C\-1

C\-2

…

C\-k｝

(C\-i

C\-j)∈E\$ if and only if \$E(C\-i)∩E(C\-j)≠(1≤i≠j≤k).\$ Then \$G\$ is 3edge colorable if and only if \$G\$ has a cycle (1

2)cover \$θ\$ such that \$G(θ)\$ is 2 or 3colorable

which gives a way to verify a bridgeless cubic graph to be 3edge colorable.

关键词

Keywords

references

[1 ]Borely JA, Murty USR. Graph Theory Coith Applileitions[M]. L ondon:Macmillan, 1 976.

[2 ]Seymour. Sums of circuits[A]. in:Bondy JA, Murty U S R. Graph Theory and Related to pics[C]. New York:Academic Press, 1 979. 3 41 -3 55.

[3 ]Szekers G. Polyhedral Decomposition of Cubic Graphs[J]. J. Austral Math Ssoc, 1 973 , 8:3 67-3 87.

Celmins U A. On cubic graphs that do not have edge 3 -coloring. Ph D thesis, epartment of combinatorics and Optimization[M]. Canada:University of Waterloo, Water-loo, 1 984.

Huck A, Lochel M. Five cycle double cover of some cubic graphs[J]. Joural of combin Theory, 1 995, 63 (B):1 1 9-1 2 5.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰