k彩色遷移問題とは，無向グラフとその２つのk頂点彩色が与えられた際に，片方の彩色からもう片方の彩色へ，k頂点彩色であることを保ったまま，一度に一つの頂点の色を変えながら遷移することが可能であるか否かを判定する問題である．本講演では，ある色からある色へは直接変えることが出来ないという遷移可能性制約を考える．この制約は色を頂点とし，直接変えることのできる色の順序対を辺とする有向グラフにより与えることができる．本講演では，この有向グラフが有向サイクルであるかマルチツリーのある部分クラスに含まれる場合に，k彩色遷移問題が線形時間で解けることを示す．本講演は，藤井宗一郎氏，岩政勇仁氏，鈴木顕氏との共同研究に基づく．