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