Exact algorithms for intervalizing coloured graphs

H. L. Bodlaender, J. M. M. van Rooij

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
125 Downloads (Pure)


In the Intervalizing Coloured Graphs problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses (Formula Presented.) time. We also give an (Formula Presented.) algorithm for the case that the number of colors is not fixed.

Original languageEnglish
Pages (from-to)273-286
Number of pages14
JournalTheory of Computing Systems
Issue number2
Publication statusPublished - 1 Feb 2016


  • Exact algorithms
  • Graph algorithms
  • Interval graphs
  • Intervalizing coloured graphs
  • Pathwidth
  • Subexponential time


Dive into the research topics of 'Exact algorithms for intervalizing coloured graphs'. Together they form a unique fingerprint.

Cite this