Paper  abstract   bibtex   

@article{ Enright2012,
  abstract = {List colouring is an NP-complete decision problem even if the total number of colours is three. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving list colouring of permutation graphs with a bounded total number of colours. 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.},
  archiveprefix = {arXiv},
  arxivid = {1206.5106},
  author = {Enright, Jessica and Stewart, Lorna and Tardos, Gabor},
  eprint = {1206.5106},
  file = {:home/anhduc/Desktop/Dropbox/Mendeley Desktop/On List Colouring and List Homomorphism of Permutation and Interval Graphs - Enright, Stewart, Tardos - 2012.pdf:pdf},
  journal = {arXiv preprint},
  month = {June},
  title = {{On List Colouring and List Homomorphism of Permutation and Interval Graphs}},
  url = {https://www.dropbox.com/sh/v4blv7sito3opzn/AADetkc6bBdEe-Aroa5CdYvua/On List Colouring and List Homomorphism of Permutation and Interval Graphs - Enright, Stewart, Tardos - 2012.pdf?dl=0},
  year = {2012}
}