Publications

A. Lyons, "Acyclic and Star Colorings of Cographs," Preprint ANL/MCS-P1675-0909, September 2009. [pdf]

An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of star coloring requires that the union of any two color classes induces a disjoint collection of stars. We prove that every acyclic coloring of a cograph is also a star coloring and give a linear-time algorithm for finding an optimal acyclic and star coloring of a cograph. We also show that the acyclic chromatic number, the star chromatic number, the treewidth plus one, and the pathwidth plus one are all equal for cographs.