一些平面图的无圈边染色

一些平面图的无圈边染色

孙向勇¹,吴建良²

1. 山东经济学院统计与数学学院, 山东济南 250014; 2. 山东大学数学学院, 山东济南 250100

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 孙向勇

Acyclic edge coloring of some planar graphs

SUN Xiang-yong¹， WU Jian-liang²

1. School of Statistics and Mathematics, Shandong Economic University, Jinan 250014, Shandong, China;2. School of Mathematics and System Science, Shandong University, Jinan 250100, Shandong, China

Received:1900-01-01 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: SUN Xiang-yong

摘要/Abstract

摘要： 主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。

关键词: 平面图, 无圈边染色数, 无圈边染色, 圈

Abstract: If a planar graph G contains no i-cycles, i=3,5, and any two 4-cycles have no common edge, then the acyclic edge coloring conjecture holds. And if a planar graph G contains no 3-cycles and any two 4-cycles have no common vertex, then acyclic edge chromatic number of G is at most Δ(G)+3.

Key words: acyclic edge coloring number, acyclic edge coloring, cycle, planar graph

中图分类号:

O157.5

孙向勇,吴建良 . 一些平面图的无圈边染色[J]. J4, 2008, 43(9): 63-67 .

SUN Xiang-yong,WU Jian-liang . Acyclic edge coloring of some planar graphs[J]. J4, 2008, 43(9): 63-67 .

参考文献

相关文章 15

[1]	房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[2]	王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[3]	王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[4]	陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[5]	何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[6]	谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[7]	白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64.
[8]	朱海洋,顾毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[9]	孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129.
[10]	薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报（理学版）, 2015, 50(11): 60-66.
[11]	王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31.
[12]	孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13.
[13]	张绍华, 颜谨, 李硕. 图中相互独立的4-圈和8-圈[J]. 山东大学学报（理学版）, 2015, 50(02): 1-4.
[14]	杨陈, 马海成. 两类特殊三圈图的正负惯性指数和零度[J]. 山东大学学报（理学版）, 2015, 50(02): 32-37.
[15]	马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报（理学版）, 2014, 49(2): 18-23.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed