Linear coloring of graphs

✍ Scribed by Raphael Yuster

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 213 KB
• Volume: 185
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00209-4

✦ Synopsis

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)= Q(d3/2), thus showing that the result is optimal, up to an absolute constant factor. (~