圍長至少為5的平面圖的線性著色

彩春麗，陶黃林,彭嘉昊

圍長至少為5的平面圖的線性著色

*彩春麗1，陶黃林1,彭嘉昊2

(1.井岡山大學(xué)數(shù)理學(xué)院，江西，吉安 343009；2.華中科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，湖北，武漢 430074）

圍長；平面圖；線性著色；線性色數(shù)

0 引言

1 符號說明

2 主要結(jié)果

得

給出權(quán)值分配規(guī)則如下：

[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]．?dāng)?shù)學(xué)研究，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-），女，河南商丘人，助教，碩士，主要從事圖論及其應(yīng)用研究（E-mail:caichunli_0370@126.com）；

陶黃林(1981-），女，湖北黃岡人，講師，主要從事運籌學(xué)研究（E-mail:jgsxythl@126.com）；

彭嘉昊(2000-），男，江西南昌人，華中科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院應(yīng)用數(shù)學(xué)專業(yè)2018級本科生（E-mail:1434905468@qq.com）.