# Tag Info

41

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 middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we ...

11

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 polynomial time. Unfortunately, our problem is not in NP. We want to find a $k$-colouring for the minimum possible $k$. Now we can find the minimum possible $k$ in ...

10

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 wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to ...

9

As far as we know, there is no simple characterization for 3-colorability. Indeed, deciding if a given graph is 3-colorable is $\sf NP$-complete. Thus, more precisely, there is likely no polynomial-time characterization for 3-colorable graphs. However, we know plenty of structured graph classes for which the problem is easy. For example, Grötzsch's theorem ...

8

You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets. The ...

7

Whenever you are interested in a (well-known) graph invariant, it's a good idea to check out ISGCI first. Have a look at graphs that have bounded chromatic number, or graphs for which computing the number is doable in polynomial time. To shortly summarize the above, one could highlight perfect graphs (a superclass of chordal graphs), and graphs of bounded ...

7

The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position. Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require ...

7

One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all ...

7

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 face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex ...

7

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 original graph $G$ has a valid coloring $\chi$, then we can color the clique $C_v$ as follows: the color $\chi(v)$ appears $p$ times, and all other colors appear $p+1$...

6

Your problem can be solved in linear time, by reduction to 2SAT. For each vertex $v$ we will have three variables $v_R,v_B,v_G$ and clauses $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. These ensure that at most one of $v_R,v_B,v_G$ is true. For each edge $(v,w)$ labeled $R$, we will add the clause $v_R \lor w_R$. If there is ...

6

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 uses all colors in $S$, each of them exactly once. What is this good for? Usually our graphs are not colored. The idea of color coding is that finding cycles (...

6

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 having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative ...

5

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 check is whether maybe the thing you're trying to prove is false, so look for a counterexample. In this case you should easily be able to find a counterexample to ...

5

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 edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using ...

5

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 two vertices $v,w$ randomly. We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph ...

5

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 is 3-colorable.

5

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 255\sqrt3$. Let r be a random number between $\sqrt{L^2-\min(2\cdot255^2, L^2)}$ and $\min(255, L)$. Let $M=\sqrt{L^2-r^2}$. Let g be a random number between $\... 5 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, learn to enumerate all possible algorithms (Turing machines), and to simulate computation of any such Turing machine on arbitrary input. Second, learn to ... 4 Hajós came up with a calculus for proving that graphs are not 3-colorable. The calculus is complete, in the sense that every non-3-colorable graph can be proved to be non-3-colorable. Pitassi and Urquhart related the strength of this proof system to the classic Extended Frege proof system: if one system is optimal (has short proofs for all true statements), ... 4 Hint: a graph is not bipartite if there is a walk of odd length from a vertex to itself. 4 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. 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. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth". But having maximum degree at most 4 alone will not work. That is,... 4 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 \over \|v\|}.$$ Now$w$will have norm$L$. Interpret$w$as a RGB color. Next, check that all three components of$w$are in the range 0..255. If yes, you've ... 4 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)$the number of solutions where the top cell is red and the bottom one blue, and$BR(N)$the number of solutions where the top cell is blue and the bottom one red. ... 4 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 can express this relationship using matrix multiplication.$ \left( \begin{array}{cc} RR(N) \\ BR(N) \end{array} \right) % = \left( \begin{array}{cc} 1 & ...

3

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 instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other. In your case, one idea that ...

3

A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That's by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn't try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness. In ...

3

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.

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