On List Colouring and List Homomorphism of Permutation and Interval Graphs. Enright, J., Stewart, L., & Tardos, G. arXiv preprint, June, 2012.
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
{"_id":"FA5ZQfYNj9HTzRgak","bibbaseid":"enright-stewart-tardos-onlistcolouringandlisthomomorphismofpermutationandintervalgraphs-2012","downloads":0,"creationDate":"2015-06-13T03:15:11.973Z","title":"On List Colouring and List Homomorphism of Permutation and Interval Graphs","author_short":["Enright, J.","Stewart, L.","Tardos, G."],"year":2012,"bibtype":"article","biburl":"https://dl.dropboxusercontent.com/u/9343921/library.bib","bibdata":{"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","Stewart, Lorna","Tardos, Gabor"],"author_short":["Enright, J.","Stewart, L.","Tardos, G."],"bibtex":"@article{ Enright2012,\n 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.},\n archiveprefix = {arXiv},\n arxivid = {1206.5106},\n author = {Enright, Jessica and Stewart, Lorna and Tardos, Gabor},\n eprint = {1206.5106},\n file = {:home/anhduc/Desktop/Dropbox/Mendeley Desktop/On List Colouring and List Homomorphism of Permutation and Interval Graphs - Enright, Stewart, Tardos - 2012.pdf:pdf},\n journal = {arXiv preprint},\n month = {June},\n title = {{On List Colouring and List Homomorphism of Permutation and Interval Graphs}},\n 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},\n year = {2012}\n}","bibtype":"article","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","id":"Enright2012","journal":"arXiv preprint","key":"Enright2012","month":"June","title":"On List Colouring and List Homomorphism of Permutation and Interval Graphs","type":"article","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","bibbaseid":"enright-stewart-tardos-onlistcolouringandlisthomomorphismofpermutationandintervalgraphs-2012","role":"author","urls":{"Paper":"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"},"downloads":0},"search_terms":["list","colouring","list","homomorphism","permutation","interval","graphs","enright","stewart","tardos"],"keywords":[],"authorIDs":[],"dataSources":["DJNCDySdY8tyWWhKE"]}