BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Selective graph coloring problem: applications and complexity
DTSTART:20160212T110000
DTEND:20160212T120000
DTSTAMP:20260406T170019Z
UID:8328948cb2ee2f077a04667e6f2fa99cb9c77abc3efe41c64d5aa299
CATEGORIES:Conferences - Seminars
DESCRIPTION:Ass. Prof. Marc Demange\, RMIT University\, School of Science 
 - Mathematical and Geospatial Sciences\,  Melbourne - Australia\nBio: HDR
  (Computer Science)\, Paris-Dauphine University\nPHD (Doctoral Thesis)\, C
 omputer Science\, Paris I UniversityResearch Master (DEA) Modeling and Mat
 hematical Methods for Economy\, Paris I University-Ecole PolytechniqueAgr
 égation (French Diploma for Teaching)\, Mathematics (Probability)Ecole No
 rmale Supérieure de Cachan (French school for teaching and research caree
 r)\, Mathematics\nIn this talk I will present the minimum Selective Graph 
 Coloring Problem\, a generalization of the standard graph coloring problem
  as well as several of its possible applications and related complexity re
 sults. Given a graph with a partition of its vertex set into several clust
 ers\, one wants to select one vertex per cluster such that the chromatic n
 umber of the subgraph induced by the selected vertices is minimum. This pr
 oblem appeared in the literature under different names for specific models
 .\nHere I will describe different models -- some already discussed in prev
 ious papers and some new ones -- in very different contexts under a unifie
 d framework based on this graph problem. Each model motivates the problem 
 in some graph classes and I will discuss the related complexity in these c
 lasses. I will also conclude by introducing the maximum version of the pro
 blem. This talk covers recent papers co-authored with T. Ekim (Bogazici Un
 iversity\, Istanbul)\, J. Monnot (CNRS\, France)\, B. Ries (University of 
 Fribourg)\, C. Tanasescu (RMIT University\, Australia) and P. Pop (Univers
 ity of Baia Mare\, Romania).
LOCATION:Room GC C2 413 http://map.epfl.ch/?q=gcc2413
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR