Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Octobre 2016

A Dual to a Classical Graph Homomorphism Theorem of Lovász

par Stefan Mengel (CNRS et Université d’Artois)

Graph homomorphism is a classical object of study in structural graph theory, with applications in many areas, like constraint satisfaction and database theory.

In this talk, I will first give a short introduction into graph homomorphisms and discuss some computational aspects. Then I will present a result that is dual to a classical result of Lovász; it roughly says that every graph is uniquely described by the number of homomorphisms it has to other graphs. I will close by sketching an application of this result in counting complexity.

This is joint work with Hubie Chen.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30