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. |