Bipartite Decomposition of Graphs Using Chromatic Number

This chapter targets to determine a decomposition of G into bipartite graphs. In a bipartite graph, the vertex set is partitioned into two independent sets. So, for a bipartite decomposition, we required independent sets. We have partitioned a given graph G into independent sets. A decomposition for G into bipartite graphs is later determined using the possible subsets of cardinality two. This process of determining the decomposition also enable us to determine all possible independent sets and hence a chromatic partition for G. Hence, a proposed algorithm can also be used for determining the chromatic number of G.