Pour chaque nombre fixe, il est possible de décider en temps polynomial si le nombre sous-chromatique de graphes d'intervalle et de permutation est au plus égal à r.
Pour chaque entier fixe r, il est possible de décider en temps sous-chromatique si le nombre polynomial des graphes d'intervalle et de permutation est au plus égal à r.