# How to partition Bipartite Graph?

Assume that $G=(V,E)$ is a bipartite graph. Then $V$ can be partitioned into two sets $L$ and $R$ so that no edge connects a pair of nodes in $L$ nor a pair of nodes in $R$. Hence, we can use one color for all nodes in $L$ and a second color for all the nodes in $R$. Hence $\chi(G)=2$.

How does one partition the following graph into two sets $L$ & $R$? Let $E = \{(0,1),(1,2),(2,3),(3,0),(3,4),(4,5),(4,6)\}$

So starting from node 0, can I say that:

$L=\{0,2,4\}$

Explanation:

• Starting at node 0, so add node 0
• Add node 2 since it is not directly connected to node 0
• Add node 4 since it is not directly connected to node 2

$R=\{1,3,5,6\}$

Explanation:

• Since we started at node 0, so add node 1 since it is to the right of node 0
• Add node 3 since it is not directly connected to node 1
• Add node 5 since it is not directly connected to node 3
• Add node 6 since it is not directly connected to node 3

Am I correct? Is there a formal method to do this?

## 1 Answer

Your partition is correct. If you know that a graph is bipartite, just pick a vertex and put it into $L$. Then put every vertex adjacent to it into $R$. Then put every as yet unclassified vertex adjacent to $R$ into $L$. Then put every as yet unclassified vertex adjacent to $L$ into $R$. Keep going until all vertices have been classified. If you do this with your graph, starting with $1\in L$, the next step puts $0$ and $2$ in $R$; the next one puts $3$ in $L$; the next puts $4$ in $R$; and the last puts $5$ and $6$ in $L$. You end up with $L=\{1,3,5,6\}$ and $R=\{0,2,4\}$, exactly the same as your decomposition, but with the labels $L$ and $R$ interchanged.

• What do you mean by "Then put every as yet"? Anyway I believe I understand your method. Thank you for this. – lucidgold Oct 12 '15 at 3:44
• @lucidgold: That’s as-yet-unclassified; it means the same as not yet classified, i.e., not yet assigned to $L$ or to $R$. A book that is as yet unread is a book that has not been read yet. You’re welcome. – Brian M. Scott Oct 12 '15 at 3:46
• Excellent, thanks again! – lucidgold Oct 12 '15 at 3:47
• @lucidgold: My pleasure! – Brian M. Scott Oct 12 '15 at 3:48