Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints.

Tomás Feder Pavol Hell Carlos S. Subi

Published in: CoRR (2019)

Keyphrases

directed graph
bounded treewidth
conp complete
np hard
worst case
np complete
constraint satisfaction
constraint programming
undirected graph
computational complexity
space complexity
spanning tree
equivalence classes
polynomial time complexity