I just added dev-libs/gecode-4.4.0 to the tree and tried to remove v3.7.3. The version bound in dep_selector is >=dev-libs/gecode-3.5.0, but dep_selector only works with the 3.x series for now, so it will need an upper bound (e.g. <dev-libs/gecode-4). There is a pull request open upstream to support gecode-4.x: https://github.com/chef/dep-selector/pull/44
*** Bug 590224 has been marked as a duplicate of this bug. ***
Fixed in dep_selector-0.1.1-r1 by limiting gecode versions as suggested by mjo.