Acyclically 4-colorable triangulations

•The problem of deciding whether a triangulation is acyclically 4-colorable is NP-complete.•Every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices.•For every acyclic 4-colorable 4-connected triangulation with exactly four odd-vertices, it follows that the subgraph induced by the four odd-vertices is triangle-free and claw-free.

An acyclic k-coloring of a graph is a proper vertex k-coloring such that every bichromatic subgraph, induced by this coloring, contains no cycles. A graph is acyclically k-colorable if it has an acyclic k-coloring. In this paper, we prove that every acyclically 4-colorable triangulation with minimum degree more than 3 contains at least four odd-vertices. Moreover, we show that for an acyclically 4-colorable triangulation with minimum degree 4, if it contains exactly four odd-vertices, then the subgraph induced by its four odd-vertices is triangle-free and claw-free.