Graph decomposition algorithms are used to form special subgraphs with some property that may be used for various applications such as routing in mobile networks. Vertex coloring is the process of assigning colors to the vertices of a graph such that every vertex receives a color that is different than its neighbors. An independent set is a subset of vertices of a graph that are not adjacent. A dominating set of a graph is a subset of its vertices with the property that each vertex in the graph is either in this set or a neighbor of a node in this set. Coloring vertices with minimum number of colors, finding a maximum independent set and a minimum dominating set are all NP-Hard problems. We review heuristic coloring, vertex cover, maximal independent set and minimal dominating set problems as in [1] in this chapter with provided Python codes using mpi4py.