Linear Coloring of Planar Graphs Without 4-Cycles

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 G is the smallest number of colors in a linear coloring of G. In this paper, we prove that if G is a planar graph without 4-cycles, then lc ${(G)le lceil frac {Delta}2rceil+8}$ , where Δ denotes the maximum degree of G.