AlgoDaily - The Two Coloring Graph Problem

The Two Coloring Graph Problem (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Quora, Two Sigma, Red Hat, Toast, Squarespace, Samsara, Akamai, Sonos, Expedia, and Qualtrics.

Question

Given a graph, can you use two colors to color each node of the graph, such that no two adjacent nodes have the same color?

The Problem

The graph coloring problem is a well-known problem in computer science. It requires coloring different nodes of the graph so that two adjacent nodes do not have the same color.

In this challenge, we'll look at a special case of this problem, where we'll determine if two colors suffice for graph coloring or not. The 2 coloring problem is also equivalent to creating a partition of a set of elements, so that two connected elements are in two different partitions.

xxxxxxxxxx
​
 
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.