تقرير
On List Colouring and List Homomorphism of Permutation and Interval Graphs
| العنوان: | On List Colouring and List Homomorphism of Permutation and Interval Graphs |
|---|---|
| المؤلفون: | Enright, Jessica, Stewart, Lorna, Tardos, Gabor |
| سنة النشر: | 2012 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, 05C15, 05C85 |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1206.5106 |
| رقم الأكسشن: | edsarx.1206.5106 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!