42 votes
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 ...
Joey Eremondi's user avatar
11 votes

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 ...
Especially Lime's user avatar
10 votes
Accepted

How to prove that 3-coloring is decidable?

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you ...
David Richerby's user avatar
7 votes
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 ...
Yuval Filmus's user avatar
7 votes

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 ...
Yuval Filmus's user avatar
7 votes
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 ...
Gregory J. Puleo's user avatar
6 votes

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 ...
Yuval Filmus's user avatar
5 votes
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 ...
D.W.'s user avatar
  • 158k
5 votes

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 ...
xskxzr's user avatar
  • 7,425
5 votes
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 ...
Yuval Filmus's user avatar
5 votes
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.
Yuval Filmus's user avatar
5 votes

Showing that 3-colorable is NP-complete

No, you couldn't say that, because it's not true. A helpful method is to prove all your claims. Don't just guess -- try to find a proof. If you're struggling to find a proof, the first thing to ...
D.W.'s user avatar
  • 158k
5 votes
Accepted

How to create RGB-colors with equal vector norm?

So how would one generate RGB vectors with a constant norm that are still valid RGB values? ($0 \le r,g,b \le 255$) There is a simpler algorithm. Let $L$ be the given norm. Verify that $0\le L\le ...
John L.'s user avatar
  • 38.8k
5 votes

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

The following roughly sketched algorithm, assuming P=NP, finds a 3 coloring of the input graph if one exists, in polynomial time. If there's no such 3 coloring, though, it never terminates. First, ...
Jirka Hanika's user avatar
5 votes

Meaning of "approximation within $n^{1−\epsilon}$"

It is unfortunate that papers in hardness of approximation use this kind of phrasing, since it is rather inaccurate. Here is what the paper actually proves (see the proof of Theorem 1.2 on page 118): ...
Yuval Filmus's user avatar
5 votes

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Morandini, NP-complete problem: partition into triangles shows that the following problem is NP-complete: Given a tripartite graph $G$ on $3n$ vertices (given together with a tripartition), determine ...
Yuval Filmus's user avatar
5 votes
Accepted

Graph Injective-Homomorphism Problem

As D.W. mentioned, $G$ is injective-homomorphic to $H$ if and only if $G$ is isomorphic to a subgraph of $H$. That is why you are "unable to find a single research paper on 'injective-...
John L.'s user avatar
  • 38.8k
5 votes

Is 2-coloring in NL or L?

The 2-coloring problem is $\mathsf{SL}$-complete. That means that there is a logspace reduction from 2-coloring to undirected accessibility (and conversely). See this paper for some references. It was ...
Nathaniel's user avatar
  • 13.9k
4 votes
Accepted

Euler graph k-coloring (np-completeness proof)

A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an ...
Yuval Filmus's user avatar
4 votes

Easy instances of the coloring problem on graphs with degree at most 4

You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. ...
Juho's user avatar
  • 22.5k
4 votes

How to create RGB-colors with equal vector norm?

Generate a random three-dimensional vector $v$ with non-negative components (you can generate each of the three components at random). Then, fix up the norm to be $L$ by setting $$w = L \cdot {v \...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Algorithms for 2-colouring a 2 x N matrix

One can view this problem as a dynamic programming problem with $3N$ subproblems. Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ ...
Tom van der Zanden's user avatar
4 votes

Algorithms for 2-colouring a 2 x N matrix

I will show you how you can improve the computational complexity of Tom's solution. Let's rewrite his recursive relationship: $$RR(N) = RR(N - 1) + 2BR(N - 1)$$ $$BR(N) = RR(N - 1) + BR(N - 1)$$ You ...
George Vidalakis's user avatar
4 votes
Accepted

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$. Let's consider the ...
HEKTO's user avatar
  • 3,088
4 votes

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^*(\min(n^3,m^2))$ time. Theory Let $P(a)$ denote the set of paths that start at $s$, go ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Graph coloring with fixed-size color classes

This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

What is a guarenteed amount of colors, depending on the graph's arboricity

Your explanation is correct. And, you can not do better than $f(a) = 2a$. For example, take a complete graph on $4$ vertices: $a,b,c,d$. The Arboricity is $2$ since $(a,b), (b,c),$ and $(c,d)$ forms ...
Inuyasha Yagami's user avatar
3 votes
Accepted

Reducing a graph without changing its chromatic number

The general idea of taking a problem instance and reducing it to a smaller one that gives the same answer is called kernelization. It's widely used in parameterized complexity theory and not just for ...
David Richerby's user avatar
3 votes
Accepted

Complexity of a graph parity-coloring problem

Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight ...
xskxzr's user avatar
  • 7,425
3 votes
Accepted

Prove np-hardness of dividing items from the lists

To prove that a problem is NP-hard, we need to reduce an NP-hard problem to it (which in this case as you mentioned would be 3-coloring). So what we are trying to do, is to map every graph $G(V,E)$ ...
Narek Bojikian's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible