0
\$\begingroup\$

The problem is:

Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be coloured such that no two adjacent vertices share the same colour using at most k colours. Source: https://www.dailycodingproblem.com/

The proposed solution uses a backtracking algorithm (https://www.dailycodingproblem.com/blog/graph-coloring), but I would like to know if just evaluating the vertice degree is enough (source: https://youtu.be/LUDNz2bIjWI?t=169).

    boolean canBeColored(int[][] adjacencyMatrix, int colors) {

    for (int row = 0; row < adjacencyMatrix.length; row++) {
        int degree = 0;
        for (int column = 0; column < adjacencyMatrix[row].length; column++) {
            if (adjacencyMatrix[row][column] == 1) {
                degree++;
            }
        }

        if (degree > colors) {
            return false;
        }
    }

    return true;
}
\$\endgroup\$
2
  • \$\begingroup\$ What programming language is this? Where is the rest of the program? \$\endgroup\$
    – pacmaninbw
    Commented Dec 26, 2019 at 14:32
  • \$\begingroup\$ It is Java, and this is the whole program. \$\endgroup\$ Commented Dec 26, 2019 at 14:41

1 Answer 1

1
\$\begingroup\$

It is not. Consider a triangle graph which has tree nodes and three edges. All vertices has degree two but three colors are required to color it. Your function would fail for that input.

In fact, the problem is NP-complete meaning that it is not known if an efficient algorithm can be constructed for solving it. So if you can do it, you'll win fame and fortune and also a very large monetary prize.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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