Acyclic coloring with few division vertices

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

Rahnuma Islam Nishat, Md. Saidur Rahman, Debajyoti Mondal, 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

subdivisionNP-completenessplanar graphacyclic coloring

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Acyclically 4-colorable triangulations ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Unnamed Item ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ Acyclic, star, and injective colouring: bounding the diameter

Uses Software

• ColPack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclically 3-colorable planar graphs
• How to draw a planar graph on a grid
• Acyclic colorings of subcubic graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Every planar graph has an acyclic 7-coloring
• Canonical ordering trees and their applications in graph drawing
• Every planar graph has an acyclic 8-coloring
• Minimum feedback vertex set and acyclic coloring.
• Acyclic colorings of graph subdivisions revisited
• Graphs with maximum degree \(6\) are acyclically \(11\)-colorable
• On acyclic colorings of planar graphs. (Reprint)
• Acyclic Coloring with Few Division Vertices
• Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation
• Acyclic Colorings of Graph Subdivisions
• Graphs with maximum degree 5 are acyclically 7-colorable
• Acyclic 5-choosability of planar graphs without adjacent short cycles
• Acyclic coloring of graphs
• The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
• Layout of Graphs with Bounded Tree-Width
• Acyclic colorings of planar graphs