彩春麗,易 華
最大度較小的圖的線性著色
*彩春麗,易 華
(井岡山大學數(shù)理學院,江西,吉安 343009)
本文研究了最大度較小的圖的線性著色問題。通過分析未著色頂點的鄰近頂點的著色情況,擴充圖的部分線性著色,利用數(shù)學歸納法證明了△() ≤ 4的非4正則圖的線性色數(shù)有l(wèi)c() ≤ 7和△() ≤ 5的非5正則圖的線性色數(shù)有l(wèi)c() ≤ 13。
最大度;線性著色;線性色數(shù)
[1] Yuster R. Linear coloring of graphs [J].Discrete Mathematics, 1998, 185:293-297.
[2] Esperet L, Montassier M, Raspaud A. Linear choosability of graphs [J].Discrete Mathematics, 2008, 308:3938-3950.
[3] 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.
[4] Liu C H, Yu G. Linear colorings of subcubic graphs[J]. European Journal of Combinatorics, 2013, 34: 1040-1050.
[5] Li C, Wang W, Raspaud A. Upper bounds on the linear chromatic number of a graph [J]. Discrete Mathematics, 2011, 311:232-238.
[6] Dong W, Lin W S. On linear coloring of planar graphs with small girth[J]. Discrete Applied Mathematics, 2014, 173: 35-44.
[7] Wang Y Q, Wu Q. Linear coloring of sparse graphs[J]. Discrete Applied Mathematics, 2012, 160: 664-772.
[8] 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 GRAPHS WITH SMALL MAXIMUM DEGREE
CAI Chun-li, YI Hua
(School of Mathematics and Physics, Jinggangshan University, Ji’an Jiangxi 343009, China)
maximum degree; linear coloring; linear chromatic number
O157.5
A
10.3969/j.issn.1674-8085.2020.05.002
1674-8085(2020)05-0005-05
2020-04-20;
2020-05-18
*彩春麗(1986-),女,河南商丘人,助教,碩士,主要從事圖論及其應用研究(Email:619662208@qq.com);
易 華(1973-),男,湖北松滋人,講師,博士,主要從事小波分析及其應用研究(Email:876145777@qq.com).