On List Coloring and List Homomorphism of Permutation and Interval Graphs

Citation

Enright J, Stewart L & Tardos G (2014) On List Coloring and List Homomorphism of Permutation and Interval Graphs. SIAM Journal on Discrete Mathematics, 28 (4), pp. 1675-1685. https://doi.org/10.1137/13090465X

Abstract
List coloring is an NP-complete decision problem even if the total number of colors is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list coloring of permutation graphs with a bounded total number of colors. More generally, we give a polynomial-time algorithm that solves the list-homomorphism problem to any fixed target graph for a large class of input graphs, including all permutation and interval graphs. 

Keywords
homomorphism; interval graph; permutation graph; list coloring

Journal
SIAM Journal on Discrete Mathematics: Volume 28, Issue 4

• 90465.pdf