Acyclic and Star Colorings of Joins of Graphs and an Algorithm for Cographs

Event Sponsor: 
LANS Informal Seminar
Start Date: 
May 20 2009 - 3:00pm to 4:00pm
Building 221, room A-261
Argonne National Laboratory
Andrew Lyons
Speaker(s) Title: 
Computation Institute

We discuss some graphs coloring problems that are related to the efficient evaluation of sparse derivative matrices. In particular, we consider the problems of finding optimal acyclic and star colorings, which model two different methods for the evaluation of Hessians. Both of these problems are known to be intractable even in severely restricted cases. We present a formula that describes the acyclic and star chromatic numbers of graphs that are decomposable with respect to the join operation, which builds a new graph from a collection of two or more disjoint graphs by adding all possible edges between them. We also show that our results lead to linear time algorithms for finding optimal acyclic and star colorings of cographs, which have the unique property that they are recursively decomposable with respect to the join and disjoint union operations.

Miscellaneous Information: