In this seminar I will discuss some topics of graph colouring in graph classes defined from a set of intervals.
Graph colouring is among the most popular problems in combinatorial optimisation. Given a simple graph, the problem is to assign a colour to each vertex so that two adjacent vertices are not of the same colour and the number of colours is minimum. Many different generalisations have also been considered.
Intervals are among the simplest objects that naturally appear in many applications. There are many popular ways to define a graph from a set of intervals of the line, but also embedded in a 2-dimension plane. The most known example is the class of interval graphs but many other graph classes like permutation graphs, overlap graphs, interval linear graphs can be defined from a similar interval structure. However these different classes have very different properties and behaviours with respect to graph colouring.
In this talk I will discuss some (generalised) graph colouring models involving these classes and some related results, in particular from the algorithmic and complexity point of view. I will conclude by an on-going work in interval colouring where intervals are used as the colours.
Related results are part of different join works with D. de Werra (Ecole Polytechnique de Lausanne), T. Ekim (Bogazici University, Istanbul), B. Ries (University of Fribourg) and C. Tanasescu (RMIT University).
About the speaker: Marc Demange holds a PhD in Computer Science from Paris I – Panthéon 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 Panthéon 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.
How to participate in this seminar:
1. Book your nearest ACE facility;
2. Notify Andriy Olenko at La Trobe University (a.olenko@latrobe.edu.au) with a cc to Darren Condon (d.condon@latrobe.edu.au) to notify you will be participating.
No access to an ACE facility? Contact Maaike Wienk to arrange a temporary Visimeet licence for remote access (limited number of licences available – first come first serve)