6
$\begingroup$

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

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

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
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Sage can compute the chromatic number... $\endgroup$ – Igor Rivin Jan 1 '16 at 16:11
  • 2
    $\begingroup$ @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)? $\endgroup$ – joro Jan 1 '16 at 16:14
  • $\begingroup$ Look at the documentation of chromatic_numer() or coloring(), and you will see that different "solver" are available inside. $\endgroup$ – Nathann Cohen Jan 2 '16 at 11:04
  • $\begingroup$ @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? $\endgroup$ – joro Jan 2 '16 at 11:49
  • $\begingroup$ 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) $\endgroup$ – Nathann Cohen Jan 2 '16 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.