The description of the checkpolicy package says: "Only required for building policies". However, it's both a buildreq and a runtime requirement in the selinux-policy package. If there is a runtime requirement, the description should be updated. Otherwise, the Requires should be dropped.
I believe you are correct. Nice catch. Fixed in selinux-policy-3.11.1-37.fc18.noarch
This bug appears to have been reported against 'rawhide' during the Fedora 19 development cycle. Changing version to '19'. (As we did not run this process for some time, it could affect also pre-Fedora 19 development cycle bugs. We are very sorry. It will help us with cleanup during Fedora 19 End Of Life. Thank you.) More information and reason for this action is here: https://fedoraproject.org/wiki/BugZappers/HouseKeeping/Fedora19
selinux-policy-3.12.1-28.fc19 has been submitted as an update for Fedora 19. https://admin.fedoraproject.org/updates/FEDORA-2013-5045/selinux-policy-3.12.1-28.fc19
Package selinux-policy-3.12.1-28.fc19: * should fix your issue, * was pushed to the Fedora 19 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing selinux-policy-3.12.1-28.fc19' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/FEDORA-2013-5045/selinux-policy-3.12.1-28.fc19 then log in and leave karma (feedback).
selinux-policy-3.12.1-28.fc19 has been pushed to the Fedora 19 stable repository. If problems still persist, please make note of it in this bug report.