On inverse chromatic number problems (Extended abstract)

Yerim Chung, Jean François Culus, Marc Demange

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We study inverse chromatic number problems in permutation graphs and in interval graphs. Given a fixed instance and a fixed integer K, the instance has to be modified as little as possible so that the newly obtained graph can be colored with K colors or less. We show that the inverse (p, k)-colorability problem (defined similarly) in permutation graphs is polynomially solvable for fixed p and k. We then propose a polynomial-time algorithm for solving inverse chromatic number problem in interval graphs where all intervals have length 1 or 2. We also show that the latter problem is NP-hard if there is a constant number of different interval lengths.

Original languageEnglish
Pages (from-to)1129-1136
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Issue numberC
Publication statusPublished - 2010 Aug

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On inverse chromatic number problems (Extended abstract)'. Together they form a unique fingerprint.

Cite this