Für jede feste Zahl kann in der Polynomialzeit entschieden werden, ob die subchromatische Anzahl der Intervall- und Permutationsgraphen höchstens r ist.
Für jede feste ganze Zahl r kann in der Polynomialzeit entschieden werden, ob die subchromatische Anzahl der Intervall- und Permutationsgraphen höchstens r ist.