# Tag Info

Accepted

### Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

There are two cases: $P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded ...
• 29.8k

### Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

If P=NP, that means there is for any given problem in NP, for example, the problem "Is $G$ $k$-colourable?", where $G$ is a finite graph and $k$ an integer, there is an algorithm to solve it in ...
Accepted

### An efficient algorithm to decide if a triangulation is 3-colourable

Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces. Pick an arbitrary triangular ...
• 278k

### Find a $\log_2(|V|)$ long cycle where each node is of different color

The idea is to use dynamic programming. For every pair of vertices $x,y$ and subset $S$ of colors, you determine whether there is a path from $x$ to $y$ of length $|S|$ (measured in vertices) which ...
• 278k
Accepted

### Graph coloring variation

The definition you are looking for is "defective coloring": A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours ...

### Graph coloring variation

I'm not familiar with this variant, but it is still NP-complete for any fixed $p$. Given a graph $G$ and an integer $c$, connect to each vertex $v$ a clique $C_v$ on $(p+1)c-1$ vertices. If the ...
• 278k
Accepted

### Equivalent Colorings of Graphs

Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices. So, here is one plausible algorithm you could use: We are given an existing coloring $C$. Pick ...
• 162k
Accepted

### Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each ...
• 278k
Accepted

### Is Graph 2-Coloring NP-Complete?

Since graph 2-coloring is in P and it is not the trivial language ($\emptyset$ or $\Sigma^*$), it is NP-complete if and only if P=NP.
• 278k

### How to reduce 3-COLOR to 42-COLOR?

For an instance of 3-COLOR, try to add a complete graph of size $k-3$, and add an edge between each new vertex and each old vertex. Now you can prove the new graph is $k$-colorable iff the old graph ...
• 7,545
Accepted

• 610