Séminaire

Pas de visio-conférence We give an algorithm which decides if a given graph B of odd-girth 2k+1 admits a homomorphism from each K_4-minor free graph of odd-girth 2k+1. The runing time is O(-V(B)-^3). Moreover the algorithm is theoretically used to find families of bounds. As an application of one such family of bounds we show that fractional chromatic number of any $K_4$-minor free graph of odd-girth 2k+1 is 2+1/k. This is a joint work with Laurent Beadou and Florent Foucaud.