Paper Info
Title
On List Coloring and List Homomorphism of Permutation and Interval Graphs.
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.
Year
DOI
Venue
2012
10.1137/13090465X
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
homomorphism,interval graph,permutation graph,list coloring
Journal
28
Issue
ISSN
Citations 
4
0895-4801
3
PageRank 
References 
Authors
0.38
5
3
Name
Order
Citations
PageRank
Jessica Enright183.89
Lorna Stewart236128.05
Gábor Tardos31261140.58