您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版）

• 论文 • 上一篇    下一篇

不含三角形的轮胎图的无圈边染色

陈光1，侯建锋2*   

  1. 1.福建教育学院, 福建 福州 350001; 2.福州大学数学与计算机科学学院, 福建 福州 350108
  • 收稿日期:2013-09-01 出版日期:2014-04-20 发布日期:2014-06-03
  • 通讯作者: 侯建锋(1981- )，男，副教授，研究方向为图论及其应用. E-mail:jfhou@fzu.edu.cn
  • 作者简介:陈光(1956- )，男，特级教师，研究方向为算法设计与分析. E-mail:chenguang56@163.com
  • 基金资助:
    国家自然科学基金资助项目(11001055); 福建省自然科学基金资助项目(2011J06001)

Acyclic edge coloring of triangle-free toroidal graphs

CHEN Guang1, HOU Jian-feng2*   

  1. 1. Fujian Institute of Education, Fuzhou 350001, Fujian, China;
    2. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, Fujian, China
  • Received:2013-09-01 Online:2014-04-20 Published:2014-06-03

PDF (PC)

1089

摘要： 图G的正常边染色称为无圈的, 如果图G中不含2-色圈。 图G的无圈边色数, 用a′(G)表示, 是使图G存在正常无圈边染色所需要的最少颜色数。证明了如果不含三角形的轮胎图G的最大度为Δ(G), 则a′(G)≤Δ(G)+3。

关键词: 无圈, 三角形, 染色

Abstract: A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. It is proved that if a trianglefree toroidal graph G has maximum degree Δ(G), then a′(G)≤Δ(G)+3.

Key words: coloring, acyclic, triangle

[1] 吴弦禧,黄丹君. mad(G)≤(13)/4的图的均匀染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 41-50.
[2] 郭亚勤,陈祥恩. 完全二部图K1,n、K2,n、K3,n的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 24-33.
[3] 田双亮,陈萍. 路的半强积与强积的距离染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 167-172.
[4] 白羽,强会英,何静. 联图Cm∨Cn的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 161-166.
[5] 胡开洋,黄明芳,马宝林. 完全二部图K12, n(12≤n≤88)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 36-43, 70.
[6] 陈宏宇. 树宽较小的图的线性荫度[J]. 《山东大学学报(理学版)》, 2024, 59(6): 25-28, 35.
[7] 王勇军,陈祥恩. 完全三部图的点被多重集可区别的一般全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 29-35.
[8] 曹静,陈祥恩. 轮与扇的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 38-46.
[9] 袁佳鑫,黄明芳. 不含K1, 3+图的强边染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 53-58.
[10] 史雅馨,刘凤霞,蔡华. Wn□Pm的r-hued染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 59-64.
[11] 雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.
[12] 朱利娜,李敬文,孙帅. 几类联图的L(2, 1)-边染色算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(8): 63-72.
[13] 常景智,杨超,姚兵. 关于图的邻和可区别全染色的新方法[J]. 《山东大学学报(理学版)》, 2023, 58(6): 35-39.
[14] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[15] 杨腾飞,徐常青. 3-退化图的全染色[J]. 《山东大学学报(理学版)》, 2022, 57(6): 61-63.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发