Abstract: | On the model of the cycle‐plus‐triangles theorem, we consider the problem of 3‐colorability of those 4‐regular hamiltonian graphs for which the components of the edge‐complement of a given hamiltonian cycle are non‐selfcrossing cycles of constant length ≥ 4. We show that this problem is NP‐complete. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 125–140, 2003 |