3-List Colouring Permutation Graphs

2011/04/26 by Enright, Jessica, Stewart, Lorna
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1104.5009

Abstract

3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation graphs.

Related

• On List Colouring and List Homomorphism of Permutation and Interval Graphs
• The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
• A polynomial 3-colorability algorithm with automatic generation of NO 3-colorability (i.e. Co-NP) short proofs
• 3-Colouring P_t-free graphs without short odd cycles
• Generalized list colouring of graphs