How to color nodes in a adjacency graph with different colors?

That's easy with Szabolcs' IGraph/M package:

Needs["IGraphM`"];
G = AdjacencyGraph[M];
colors = ColorData[97] /@ Range[4];
Graph[G,
 VertexStyle ->Thread[Range[VertexCount[G]] -> colors[[IGKVertexColoring[G, 4][[1]]]]
 ]

Alternatively, one can also use IGMinimumVertexColoring[G]; it shows that three colors are already sufficient for this graph.

---

Alternatively, the style can also be applied with IGVertexMap:

Graph[G, GraphStyle -> "BasicBlack", VertexSize -> 1.5] //
  IGVertexMap[
    ColorData[97],
    VertexStyle -> IGMinimumVertexColoring
  ]

You can also use the function MinimumVertexColoring from the Combinatorica package:

Needs["Combinatorica`"]
mvc = MinimumVertexColoring[FromAdjacencyMatrix@m];
colors = MapIndexed[#2[[1]] -> # &, ColorData[97] /@ mvc] ;
AdjacencyGraph[m, VertexSize -> 3/2, System`VertexStyle -> colors]