Acyclic and star colorings of cographs |
| |
Authors: | Andrew Lyons |
| |
Institution: | Department of Computer Science, Dartmouth College, United States |
| |
Abstract: | 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. 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 1, and the pathwidth plus 1 are all equal for cographs. |
| |
Keywords: | Acyclic coloring Star coloring Cograph Treewidth Pathwidth Triangulating colored graphs |
本文献已被 ScienceDirect 等数据库收录! |
|