AlgoDaily - The Two Coloring Graph Problem

The Basic Idea for a Solution

To implement a solution to the 2 coloring problem, we need to visit each node of the graph, which can be done via a depth-first or breadth-first traversal. Initially, none of the nodes is colored so we can assign an arbitrary color to the first node. Once the traversal begins, we check two cases for a node n:

One or more adjacent nodes of n have been assigned the same color. n can be assigned the opposite color.
Two or more adjacent nodes of n have been assigned opposite colors. It is not possible to assign n a valid color.

These two cases are shown in the figure below. The gray node has to be assigned a color.

xxxxxxxxxx
  assert.equal(twoColorGraph(N, dislikes), false);
 
var assert = require('assert');
​
var twoColorGraph = function (N, d) {
  //your code here
};
​
try {
  N = 4;
  dislikes = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
  ];
  assert.equal(twoColorGraph(N, dislikes), true);
​
  console.log('PASSED: ' + 'First Test');
} catch (err) {
  console.log(err);
}
​
try {
  N = 4;
  dislikes = [
    [0, 1, 1, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 1],

OUTPUT

Results will appear here.