RMIT University, School of Sciences, Melbourne, Victoria St., Australia
February 12, 2016, 11:00, Room GC C2 413 (click here for the map)
In this talk I will present the minimum <em>Selective Graph Coloring Problem</em>, a generalization of the standard graph coloring problem as well as several of its possible applications and related complexity results. Given a graph with a partition of its vertex set into several <em>clusters</em>, one wants to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared in the literature under different names for specific models. Here, I will describe different models -- some already discussed in previous papers and some new ones -- in very different contexts under a unified framework based on this graph problem. Each model motivates the problem in some graph classes and I will discuss the related complexity in these classes. I will also conclude by introducing the maximum version of the problem. This talk covers recent papers co-authored with T. Ekim (Bogazici University, Istanbul), J. Monnot (CNRS, France), B. Ries (University of Fribourg), C. Tanasescu (RMIT University, Australia) and P. Pop (University of Baia Mare, Romania).
Marc Demange holds a PhD in Computer Science from Paris I - Pantheon Sorbonne University (1994) and an Habilitation Thesis in Computer Science from Paris Dauphine University (2000). After his PhD he has held a position of Assistant Professor in Computer Science at Paris 1 Pantheon Sorbonne University. In 2001 he was appointed Associate Professor in Operational Research at ESSEC Business School (Paris - Singapore) and has held a position of full Professor from 2005 to 2014. Meanwhile he has also held several management positions at the same institution: Vice Dean of the Faculty, Associate Dean for Research and Director of ESSEC Romania Centre (in Bucharest). Since 2014 he is Associate Professor in Mathematical Sciences at RMIT University, Melbourne, Australia and in charge of the Bachelor of Science in Mathematics. During his career he has taught a large range of topics in Computer Science, Operational Research and Discrete Mathematics. His research interests, in Combinatorial Optimisation, are centred around the notion of efficient algorithms with performance guarantees, mainly polynomial approximation, complexity theory, algorithmic graph theory, online algorithms and inverse combinatorial optimisation. He is (co)author of more than 50 papers in international journals or book chapters.