Acyclic and Star Colorings of Cographs

Details Acyclic and Star Colorings of Cographs Acyclic and Star Colorings of Cographs

2011-03-29

arxiv.org/abs/1103.5531v1

Computer Science

Data Structures and Algorithms

11 pages, 4 figures

Scientific paper

An \emph{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 \emph{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. If the graph is given in the form of a cotree, the algorithm runs in O(n) time. 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.

Affiliated with

Also associated with

No associations

Rating

Acyclic and Star Colorings of Cographs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acyclic and Star Colorings of Cographs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic and Star Colorings of Cographs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162607