Acyclic coloring with few division vertices

DOI10.1016/j.jda.2013.08.002zbMath1334.05041WikidataQ60608613 ScholiaQ60608613MaRDI QIDQ396683

Md. Saidur Rahman, Debajyoti Mondal, Rahnuma Islam Nishat, S. H. Whitesides

Publication date: 13 August 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.08.002

zbMATH Keywords

subdivision; NP-completeness; planar graph; acyclic coloring

Mathematics Subject Classification ID

05C38: Paths and cycles

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• ColPack