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
  • 1
    $\begingroup$ The chromatic number is at most $4$. $\endgroup$
    – joro
    Jan 1, 2016 at 10:49

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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