Para cada número fijo, es posible decidir en tiempo polinomial si el número subcromático de intervalos y los gráficos de permutación es a lo sumo r.
Para cada entero fijo r, es posible decidir en tiempo subcromático si el número polinomial de gráficos de intervalo y permutación es a lo sumo r.