# Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices.

Each vertex has exactly 6 neighbors. $P$ is connected $Q$ if $P$ can be obtained from $Q$ by swapping 0 with another element. For example, 0112233 is connected to 1012233, 1102233, 2110233, 2112033, 3112203, 3112230.

Question: What is the chromatic number of graph $G?$ Is $G$ 3-colorable?

What we've proved: $G$ is not a perfect graph. It has many odd holes with length $\geq 11$.

• The chromatic number is at most $4$. – joro Jan 1 '16 at 10:49

If I constructed the graph correctly, according to a program the chromatic number is $4$, so the graph is not 3 colorable.

Got the same result after converting the problem to SAT and ran certified UNSAT solver.

The proof for unsatisfiability was only about 11MB.

The computation took few minutes and the 4-coloring was found very fast.

The graph was constructed with sage program:

def graphperm123():
S=Permutations([0,1,1,2,2,3,3])
E=[]

for u in S:
u=list(u)
i=u.index(0)
for j in xrange(len(u)):
if j==i:  continue
v=u[:]
a=v[j]
v[j]=0
v[i]=a
E += [(tuple(u),tuple(v))]
G=Graph(E,multiedges=False,loops=False)
return G

• Sage can compute the chromatic number... – Igor Rivin Jan 1 '16 at 16:11
• @IgorRivin I know this, but I gave up sage after reasonable for me time. How long does it take in sage? And do you use .chromatic_number() or first_coloring(3)? – joro Jan 1 '16 at 16:14
• Look at the documentation of chromatic_numer() or coloring(), and you will see that different "solver" are available inside. – Nathann Cohen Jan 2 '16 at 11:04
• @NathannCohen OK, I looked. What is the best wall clock time to show it is on 3-colorable in sage you have? Do you get a certificate like the certified UNSAT? – joro Jan 2 '16 at 11:49
• It took 361 seconds on my computer (with CPLEX installed, and algorithm='milp') to prove that the chromatic number is 4, and have the coloring. No certificate that it is not 3-colorable, however (though it was proved that it is not 3-colorable) – Nathann Cohen Jan 2 '16 at 12:25