摘要
设c是图G的一个顶点染色,如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色.我们首先证明了环面图上的一个Lebesgue型定理,作为其应用证明了对任一个围长不小于5的环面图G,除非△(G)=4而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面,G一定是(「△(G)/2」+4)-线性列表可染色的.这一结果推广和改进了一些已知结论.
A coloring of a graph G is said to be linear if any two color classes induce an acyclic subgraph of maximum degree at most 2.In this paper,we first prove a Lebesgue＇s type theorem concerning the structure of toroidal graphs.As a consequence of this result,we show that every toroidal graph G of girth at least 5 can be （「△（G）/2」 ＋ 4）-linear list colorable,unless △（G）=4 and G has a subgraph containing only faces of degree five of which each is incident with three vertices of degree 3 and two vertices of degree 4.This generalizes and improves some known results.
出处
《中国科学：数学》
CSCD
北大核心
2011年第5期477-484,共8页
Scientia Sinica：Mathematica
基金
南京师范大学创新项目
江苏省教育厅自然科学基金(批准号:08KJB110008)
国家自然科学基金(批准号:10801077)资助项目
关键词
环面图
围长
线性列表染色
toroidal graph
girth
linear list coloring
