Acyclic and star coloring of P4-reducible and P4-sparse graphs

摘要

An acyclic coloring of a graph G is a proper vertex coloring such that G contains no bicolored cycles. The more restricted notion of star coloring of G is an acyclic coloring in which each path of length 3 is not bicolored. In this paper, we mainly study on the acyclic and star coloring of P4-reducible and P4-sparse graphs. Moreover, we list polynomial-time algorithms for giving an optimal acyclic or star coloring of a P4-reducible or P4-sparse graph.