Abstract :
A proper vertex coloring of a graph is called linear if the subgraph induced by the vertices colored by any two colors is a set of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by lc(G), is the minimum number of colors in a linear coloring of G. Extending a result of Alon, McDiarmid and Reed concerning acyclic graph colorings, we show that if G has maximum degree d then lc(G) = O(d3/2). We also construct explicit graphs with maximum degree d for which lc(G) = Ω (d3/2), thus showing that the result is optimal, up to an absolute constant factor.
