Defective acyclic colorings of planar graphs

Abstract

This paper studies two variants of defective acyclic coloring of planar graphs. For a graph $G$ and a coloring $\phi$ of $G$, a 2CC transversal is a subset $E^{\prime }$ of $E(G)$ that intersects every 2-colored cycle. Let $k$ be a positive integer. We denote by $m_k(G)$ the minimum integer $m$ such that $G$ has a proper $k$-coloring which has a 2CC transerval of size $m$, and by $m_k^{\prime }(G)$ the minimum size of a subset $E^{\prime }$ of $E(G)$ such that $G-E^{\prime }$ is acyclic $k$-colorable. We prove that for any $n$-vertex $3$-colorable planar graph $G$, $m_3(G)\le n-3$ and for any planar graph $G$, $m_4(G)\le n-5$ provided that $n\ge 5$. We show that these upper bounds are sharp: there are infinitely many planar graphs attaining these upper bounds. Moreover, the minimum 2CC transversal $E^{\prime }$ can be chosen in such a way that $E^{\prime }$ induces a forest. We also prove that for any planar graph $G$, $m_3^{\prime }(G)\le (13n-42)/10$ and $m_4^{\prime }(G)\le (3n-12)/5$.