Linear coloring of graphs embeddable in a surface of nonnegative characteristic

• DOI: 10.1007/s11425-008-0143-7
• Publication Date: 2009-05-08T06:09:12Z
• Authors: WeiFan Wang; Chao Li
• Keywords: Fractional coloring; Edge Coloring; Complete coloring; List coloring; Disjoint sets

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G.