0
$\begingroup$

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$?

enter image description here

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "Then put every as yet"? Anyway I believe I understand your method. Thank you for this. $\endgroup$ – lucidgold Oct 12 '15 at 3:44
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 12 '15 at 3:46
  • $\begingroup$ Excellent, thanks again! $\endgroup$ – lucidgold Oct 12 '15 at 3:47
  • $\begingroup$ @lucidgold: My pleasure! $\endgroup$ – Brian M. Scott Oct 12 '15 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.