Linear coloring of graphs without 4-cycles and embeddable in a surface of nonnegative Euler characteristic

Abstract

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number lc(G) of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that if G is a graph without 4-cycles that is embeddable in a surface of nonnegative Euler characteristic, then lc(G) ≤ [Δ/2] +11, where Δ denotes the maximum degree of G.