92 citations · 608 across the 67 of their papers we have counts for
5 papers · 1 filter
Distributed coloring of graphs with an optimal number of colors
Étienne Bamas, Louis Esperet
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e.\ with the minimum number of colors) in the LOCAL model of comput…
Boxicity, poset dimension, and excluded minors
Louis Esperet, Veit Wiechert
In this short note, we relate the boxicity of graphs (and the dimension of posets) with their generalized coloring parameters. In particular, together with known estimates, our res…
Single-conflict colouring
Zdeněk Dvořák, Louis Esperet, Ross J. Kang +1
Given a multigraph, suppose that each vertex is given a local assignment of colours to its incident edges. We are interested in whether there is a choice of one local colour pe…
Distributed coloring in sparse graphs with fewer colors
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet +1
This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar gr…
Separation choosability and dense bipartite induced subgraphs
Louis Esperet, Ross J. Kang, Stéphan Thomassé
We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that…