1
$\begingroup$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability.

For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added and the graph $G/uv$ is obtained by merging the two vertices.

According to wikipedia

$$P(G,k)= P(G+uv, k) + P(G/uv,k) \qquad (1) $$

The recursion for computing $P(G,x)$ modulo $x-3$ is siginificantly faster since induced $K_4$ stops computing further.

Consider the following naive algorithm for checking 3-colorability using $P(G,x) \pmod{x-3}$.

 function color3(G: connected graph)
 #returns 0 if G is not 3-colorable, otherwise reports it is and stops
 if G contains induced K_4 
     return 0
 if G is a clique on 3 or less vertices 
     report '3-colorable'. Stop.
 if we can add edge uv which induces K_4 in G 
     return color3(G/uv) #the induced K_4 contributes 0 to the sum
 #the above makes the problem strictly smaller
 #this might be greatly improved by trying to induce K_4-e
 [C] pick the lexicographic first non-adjacent u,v and return color3(G+uv)+color3(G/uv)

One call to color3 is polynomial, so the complexity depends on the number of double recursion in [C].

According to Wikipedia the worst case for computing (1) is $\phi^{n+m}$. 3-coloring 4-regular graphs is NP-complete, so for 4-regular it is $\phi^{3n}$.

Appears to me terminating by induced $K_4$ would greatly improve the running time.

Questions:

Q1 What is the complexity of color3?

$O(c^n)$ for small $c$ will be of practical interest. $2^{o(n)}$ might indicate complexity collapse.

Q2 How to improve [C]?

There might be other improvements like other 4-chromatic subgraph or $F$ being in a graph class where coloring is polynomial.

Experimental results:

For several 4-regular graphs on 246 vertices which are the line graphs of 3-regular graphs color3 found 3-coloring in less than a minute in sage 6.2 implementation. For several smaller graphs which are not 3-colorable it correctly returned 0. For reduction SAT to 3-color the running time was fast too.

Sage implementation: https://gist.github.com/jor0/039127ab69dd8934c105

$\endgroup$

closed as off-topic by D.W., Kaveh, Lev Reyzin Sep 25 '17 at 0:37

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – D.W., Kaveh, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.