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



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


The program is:
<https://code.google.com/p/graphcol/>


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

```

