Minimum feedback vertex set and acyclic coloring.

DOI10.1016/S0020-0190(02)00265-XzbMath1042.68090OpenAlexW1999519812MaRDI QIDQ1853123

Guillaume Fertin, Emmanuel Godard, Andre Raspaud

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00265-x

zbMATH Keywords

1-planar graphsGraph algorithmsPlanar graphsOuterplanar graphs-treesAcyclic coloringMinimum feedback vertex set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

Acyclic colorings of subcubic graphs ⋮ A feedback vertex set of 2-degenerate graphs ⋮ Feedback vertex sets in mesh-based networks ⋮ Acyclic coloring of graphs with maximum degree 7 ⋮ Robust Connectivity of Graphs on Surfaces ⋮ Acyclic coloring with few division vertices ⋮ Maximum induced forests in graphs of bounded treewidth ⋮ Unnamed Item ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ The decycling number of outerplanar graphs ⋮ Large induced forests in planar graphs with girth 4 ⋮ Acyclic vertex coloring of graphs of maximum degree six ⋮ \(\mathcal Q\)-Ramsey classes of graphs ⋮ A polyhedral study of the acyclic coloring problem ⋮ A polyhedral study of the acyclic coloring problem ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ On acyclically 4-colorable maximal planar graphs ⋮ Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth

Cites Work

• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Feedback vertex set in hypercubes
• Almost exact minimum feedback vertex set in meshes and butterflies
• On acyclic colorings of planar graphs
• Wavelength Conversion in Optical Networks
• Acyclic Colourings of Planar Graphs with Large Girth
• Graph Classes: A Survey
• Decycling graphs
• The chromatic number of oriented graphs
• Feedback vertex set on cocomparability graphs
• Acyclic colorings of planar graphs
• Acyclic colouring of 1-planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum feedback vertex set and acyclic coloring.