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?
Best 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.