𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum feedback vertex set and acyclic coloring

✍ Scribed by Guillaume Fertin; Emmanuel Godard; André Raspaud

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
132 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In the feedback vertex set problem, the aim is to minimize, in a connected graph G = (V , E), the cardinality of the set V (G) ⊆ 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.

📜 SIMILAR VOLUMES

Minimum feedback vertex sets in shuffle-
Minimum feedback vertex sets in shuffle-based interconnection networks
✍ Rastislav Královič; Peter Ružička 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 120 KB

Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G. Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some