Minimum feedback vertex set and acyclic coloring.
type: Item
instance of: scholarly article
title: Minimum feedback vertex set and acyclic coloring.
zbMATH Open document ID: 1042.68090
DOI: 10.1016/S0020-0190(02)00265-X
author: Guillaume Fertin
author: Emmanuel Godard
author: André Raspaud
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: In the feedback vertex set problem, the aim is to minimize, in a connected graph \(G=(V,E),\) the cardinality of the set \(\overline V(G)\subseteq V\), whose removal induces an acyclic subgraph. In this paper, we show an interesting relationship between the minimum feedback vertex set problem and the acyclic coloring problem (which consists in coloring vertices of a graph \(G\) such that no two colors induce a cycle in \(G).\) Then, using results from acyclic coloring, as well as other techniques, we are able to derive new lower and upper bounds on the cardinality of a minimum feedback vertex set in large families of graphs, such as graphs of maximum degree 3, of maximum degree 4, planar graphs, outerplanar graphs, 1-planar graphs, \(k\)-trees, etc. Some of these bounds are tight (outerplanar graphs, \(k\)-trees), all the others differ by a multiplicative constant never exceeding 2.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856465
zbMATH Keywords: Minimum feedback vertex set
zbMATH Keywords: Acyclic coloring
zbMATH Keywords: Planar graphs
zbMATH Keywords: Outerplanar graphs
zbMATH Keywords: 1-planar graphs
zbMATH Keywords: -trees
zbMATH Keywords: Graph algorithms
MaRDI profile type: Publication
cites work: Decycling graphs
cites work: On acyclic colorings of planar graphs
cites work: Acyclic colouring of 1-planar graphs
cites work: Acyclic Colourings of Planar Graphs with Large Girth
cites work: Graph Classes: A Survey
cites work: Q4281625
cites work: Q4180377
cites work: Feedback vertex set on cocomparability graphs
cites work: Q3145802
cites work: Feedback vertex set in hypercubes
cites work: Acyclic colorings of planar graphs
cites work: Wavelength conversion in optical networks
cites work: A linear-time algorithm for the weighted feedback vertex problem on interval graphs
cites work: Almost exact minimum feedback vertex set in meshes and butterflies
cites work: The chromatic number of oriented graphs
cites work: Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
full work available at URL: s0020-0190(02)00265-x
OpenAlex ID: W1999519812
description: scientific article; zbMATH DE number 1856465