Skip to main content
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
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
  • 162k
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

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,545
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
  • 39k
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
  • 39k
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
  • 15.9k
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
  • 162k
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.6k
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,098
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
  • 162k
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
  • 162k
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

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,545
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
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

Can one truly build a schedule from graph coloring?

[...] is this feasible in a real world scenario? I'm not sure. But note that determining the chromatic number of a graph and determining the minimum number of timeslots needed to schedule lectures ...
David Richerby's user avatar
3 votes

Algorithms for 2-colouring a 2 x N matrix

To complement Tom's answer: the coefficient of $x^n$ of the generating function $G(x)=\frac{1+x}{1-2x-x^2}$ is $$[x^n]G(x)=\frac{\sqrt{2}+1}{2}\left(\frac{1}{\sqrt{2}-1}\right)^n-\frac{\sqrt{2}-1}{2}\...
Marcus Ritt's user avatar
3 votes

Algorithms for 2-colouring a 2 x N matrix

This answer fills the gap in the accepted answer by Tom van der Zanden, where the generating function is given by look-up magic without proper justification. This answer also produces the closed form ...
John L.'s user avatar
  • 39k

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