An Upper Bound On The Chromatic Number Of The Square Graph Of Sparse Graphs

The square G2 of a graph G is a graph such that V(G)=V(G2)and uv ? E(G2)if and only if the distance between u and v is at most two.A k-vertex-coloring of G is a mapping c:V(G)?[k];if u?v,c(u)? c(v),then c is proper.The chromatic number ?(G2)of G2 is the minimum k for which G2 has a proper k-vertex-coloring.By definition,?(G2)??(G)+1.Using the discharging method,we prove that if mad(G)<4 and ?(G)? 7,then ?(G2)? 3?(G)+1.In addition,if mad(G)? 4 and?(G)? 8,then ?(G2)?3?(G)+5.