On List Colouring and List Homomorphism of Permutation and Interval Graphs. Enright, J., Stewart, L., & Tardos, G. arXiv preprint, June, 2012.
On List Colouring and List Homomorphism of Permutation and Interval Graphs [link]Paper  abstract   bibtex   
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.
@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}
}

Downloads: 0