# Tag Info

42

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 ...

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

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

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 ...

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

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$...

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 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 ... 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 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 & ...

4

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 set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. ...

4

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 size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$. So, you should not expect any ...

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

[...] 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 with a given pattern of conflicts are exactly the same problem. So, if the scheduling problem can't be feasibly solved by colouring, it can't be feasibly solved ...

3

Graph coloring problems are widely applicable to the problem of scheduling. Consider a University, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as ...

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