环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.

A Lebesgue's type theorem on toroidal graphs and its application to linear coloring

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.