Acyclic colorings of graph subdivisions revisited

DOI10.1016/j.jda.2012.06.001zbMath1257.05045OpenAlexW2063861912MaRDI QIDQ1932357

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

Publication date: 18 January 2013

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

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

zbMATH Keywords

subdivisionNP-completeacyclic coloringtriangulated plane graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Acyclically 4-colorable triangulations ⋮ Acyclic coloring with few division vertices ⋮ On b-acyclic chromatic number of a graph ⋮ Acyclic 3-coloring of generalized Petersen graphs

Uses Software

• ColPack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to draw a planar graph on a grid
• Acyclic colorings of subcubic graphs
• Greedy drawings of triangulations
• Every planar graph has an acyclic 7-coloring
• Every planar graph has an acyclic 8-coloring
• On acyclic colorings of planar graphs. (Reprint)
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
• Acyclic Colorings of Graph Subdivisions
• Acyclically 3-Colorable Planar Graphs
• Acyclic coloring of graphs
• CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Layout of Graphs with Bounded Tree-Width
• On the Queue Number of Planar Graphs
• Acyclic colorings of planar graphs

This page was built for publication: Acyclic colorings of graph subdivisions revisited