Evènement pour le groupe GT Graphes et Applications

Date 2015-09-18  14:00-15:00
TitreHomomorphism bounds for K4-minor-free graphs 
RésuméA homomorphism of graph G to graph H is a function h from V(G) to V(H) which preserves the edges, i.e. if u,v are adjacent in G, then h(u),h(v) are adjacent in H. Homomorphisms extend the classic notion of proper graph colourings. Given a graph class C, an interesting optimization question is whether there is a graph to which all members of C admit a homomorphism (this graph is called a bound for C). If there exists one, what is the smallest order of such a bound? For example, all planar graphs admit a homomorphism to the graph K4 (this is the Four Colour Theorem), but no smaller graph is a bound. In this talk, we discuss the related problem of determining bounds for planar graphs and their subclasses, with some additional girth restrictions. Our focus will be on K4-minor-free graphs, i.e. series-parallel graphs. This is joint work with Laurent Beaudou and Reza Naserasr.  
LieuSalle 178 
OrateurFlorent Foucaud 

Aucun document lié à cet événement.

Retour à l'index