On List Colouring and List Homomorphism of Permutation and Interval Graphs

2012/06/22 by Jessica Enright, Enright, Jessica, Lorna Stewart +3 · 1 citation
Computer Science · #05C15 #05C85 #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1206.5106

openalex publication_date 2012/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• The Peculiarities of Extending Queue Layouts

Related

• 3-List Colouring Permutation Graphs
• The complexity of the list homomorphism problem for graphs
• Generalized list colouring of graphs
• The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
• Graph Isomorphism Restricted by Lists