New upper bounds on linear coloring of planar graphs

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. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has (1) lc(G) ≤ Δ + 21 if Δ ≥ 9; (2) $lc(G) leqslant leftlceil {tfrac{Delta } {2}} rightrceil + 7$ if g ≥ 5; (3) $lc(G) leqslant leftlceil {tfrac{Delta } {2}} rightrceil + 2$ if g ≥ 7 and Δ≥ 7.