我要吃瓜

Article

On List Coloring and List Homomorphism of Permutation and Interval Graphs

Details

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

StatusPublished
Publication date31/12/2014
Publication date online09/10/2014
Date accepted by journal07/07/2014
URL
PublisherSociety for Industrial and Applied Mathematics
ISSN0895-4801
eISSN1095-7146

Files (1)