ESPERET , Louis

In this paper we study fractional coloring from the angle of distributed computing. Fractional coloring is the linear relaxation of the classical notion of coloring, and has many applications, in particular in scheduling. It is known that for every real $\alpha>1$ and integer $\Delta$, a fractional coloring of total weight at most...

Lovász and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear...

A $k$-frugal colouring of a graph~$G$ is a proper colouring of the vertices of~$G$ such that no colour appears more than~$k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and...

We show that every cubic bridgeless graph G has at least 2|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.