Colloquium Details
Acyclic Edge Coloring: Some Recent Developments
| Author: | C.R. Subramanian Institute of Mathematical Sciences, India |
|---|---|
| Date: | June 12, 2007 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
An acyclic edge colouring of a graph is a proper edge colouring in which there is no bichromatic (2-colored) cycle. That is, the union of any two color classses forms a forest. Acyclic chromatic index is the minimum number of colors used in such a colouring. Estimating the acyclic chromatic index is an interesting and difficult problem both from a theoretical and an algorithmic point of view and has potential applications in scheduling. Even for highly structured graphs, this number is yet to be determined. We will give an overview of some recent results obtained by us for estimating this invariant. We will sketch both theoretical and constructive results. The proof arguments are either based on structural aspects or on probabilistic tools.
Biography
C.R. Subramanian is an Associate Professor at IMSc. He graduated with a Ph.D. in Computer Science and Engineering from Indian Institute of Science, Bangalore, India in 1995. He was an Assistant Professor at Indian Institute of Technology, Guwahati, India during 1996-98. Post Doctoral Fellow at Max-Planck Institute fur Informatik, Saarbrucken, Germany during 1998-2000.
C.R. Subramanian has been with the TCS group of The Institute of Mathematical Sciences, Chennai since 2000. His research interests include design and analysis of graph algorithms, probabilistic combinatorics, random graphs, graph theory. He has 16 journal publications and 14 conference publications with some overlap between them. He was also a PC member of FSTTCS-2004 and is presently a PC member of FSTTCS-2007.