On the Complexity of Ordered Colorings
From MaRDI portal
Publication:3629479
DOI10.1137/060676222zbMath1223.05073MaRDI QIDQ3629479
Ján Maňuch, Arvind Kumar Gupta, Jan van den Heuvel, Xiaohong Zhao, Ladislav Stacho
Publication date: 27 May 2009
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/7f100266cb6ab056403fe272a1cfb25dd43b4f7d
complexity; graph coloring; NP-completeness; polynomial algorithm; ordered coloring; directed graph homomorphism
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items