On the Chromatic Number of Path Graph P_3(G)

Let G be a graph. The path graph P3(G) of G is obtained by representing the paths P3 in G by vertices and joining two vertices whenever the corresponding paths P3 in G form a path P4 or a cycle C3. In this paper, we show that for a triangle-free graph G,χ(P3(G))≤β(G), where β(G) is the vertex covering number of G. For a connected graph G of order at least 3, χ(P3(G))≤2 if and only if G is bipartite. Furthermore, χ(P3(G))=1 if and only if G is a star. For a K4-subdivision graph G, 2≤χ(P3(G))≤3. For a series-parallel graph or an outerplanar graph G, χ(P3(G))≤3.