Seminar Details:

LANS Informal Seminar
"Acyclic and Star Colorings of Joins of Graphs and an Algorithm for Cographs"

DATE: May 20, 2009

TIME: 15:00:00 - 16:00:00
SPEAKER: Andrew Lyons, Computation Institute
LOCATION: Building 221, room A-261, Argonne National Laboratory

Description:
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.


 

Please send questions or suggestions to Debojyoti Ghosh: ghosh at mcs dot anl dot gov.