En t-interval representation av en graf uttrycker det som skärningskurvan för en familj av undergrupper av den verkliga linjen. Varje vertex tilldelas en uppsättning bestående av som mest t separerade slutna intervall, på ett sådant sätt att hörnen är intilliggande om och endast om något intervall för den ena skär något intervall för den andra. Intervallet i(G) för en graf G är det minsta antalet t så att G har en t-representation. Vi bevisar att för varje fast värde av t med t ~2, bestämma om i(G)5 t är NP-komplett.
Slutligen är det NP-hårdt att avgöra om en given graf är t-interval för t ≥ 2 REF.
Recognizing graphs with fixed interval number is NP-complete
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}