围长至少为5的平面图的线性着色

彩春丽，陶黄林,彭嘉昊

围长至少为5的平面图的线性着色

*彩春丽1，陶黄林1,彭嘉昊2

(1.井冈山大学数理学院，江西，吉安 343009；2.华中科技大学数学与统计学院，湖北，武汉 430074）

围长；平面图；线性着色；线性色数

0 引言

1 符号说明

2 主要结果

得

给出权值分配规则如下：

[1] Yuster R. Linear coloring of graphs[J]. Discrete Math, 1998, 185: 293-297.

[2] Raspaud A, Wang W F. Linear coloring of planar graphs with large girth[J]. Discrete Math, 2009,309:5678-5686.

[3] Dong W, Xu B G, Zhang X Y. Improved bounds on linear coloring of plane graphs[J]. Sci. China Math, 2010, 53(7): 1895-1902.

[4] Liu B, Liu G Z. New upper bounds on linear coloring of planar graphs[J]. ActaMathematicaSinica,English Series, 2012, 28(6):1187-1196.

[5] 王侃,王维凡．围长至少为5的平面图的线性染色[J]．数学研究，2011，44(1):76-85．

[6] Dong W, Lin W S. On linear coloring of planar graphs with small girth[J]. Discrete Applied Mathematics, 2014, 173: 35-44.

[7] Cai C L,Xie D Z, Yang W J. A result on linear coloring of planar graphs[J]. Information Processing Letters, 2012, 112(22): 880-884.

[8] Wang Y Q, Wu Q. Linear coloring of sparse graphs[J]. Discrete Applied Mathematics, 2012, 160: 664-772.

[9] Wang W F, Wang Y Q. Linear coloring of planar graphs without 4-cycles[J]. Graphs and Combinatorics,2013, 29: 1113-1124

LINEAR COLORING OF PLANAR GRAPHS WITH GIRTH AT LEAST 5

*CAI Chun-li1, TAO Huang-lin1, PENG Jia-hao2

（1.School of Mathematics and Physics, Jinggangshan University, Ji’an, Jiangxi 343009, China;School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan, Hubei 430074, China）

girth; planar graphs; linear coloring; linear chromatic number

O157.5

A

10.3669/j.issn.1674-8085.2021.03.002

1674-8085（2021）03-0008-04

2021-01-09；

2021-02-19

*彩春丽(1986-），女，河南商丘人，助教，硕士，主要从事图论及其应用研究（E-mail:caichunli_0370@126.com）；

陶黄林(1981-），女，湖北黄冈人，讲师，主要从事运筹学研究（E-mail:jgsxythl@126.com）；

彭嘉昊(2000-），男，江西南昌人，华中科技大学数学与统计学院应用数学专业2018级本科生（E-mail:1434905468@qq.com）.