A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More)

DOI10.1137/110826813zbMath1254.05056MaRDI QIDQ3143294

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

Publication date: 29 November 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110826813

zbMATH Keywords

3-compatible coloring; constrained satisfaction problem (CSP); list matrix partition; stubborn problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)