Hits :

First Author : 王侃

Affiliation of Author(s): 数理与信息工程学院

Date of Publication : 2010-01-01

Document Type : 期刊

Journal : 高校应用数学学报A辑

Issue : 第4期

Page Number : 487-495

ISSN : 1000-4424

Translation or Not : no

Key Words : 平面图；线性染色；围长；最大度

Abstract : 如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.论文证明了对于每一个最大度为△(G)围长至少为6的平面图G有lc(G)≤「(Δ(G))/2]+3,并且当△(G)■{4,5,…,12}时, lc(G)≤「(Δ(G))/2」+2.