Articles soumis

N. Bousquet et M. Heinrich, A polynomial version of Cereceda's conjecture

Let `k` and `d` be such that `k \ge d+2`. Consider two `k`-colourings of a `d`-degenerate graph `G`. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. The `k`-reconfiguration graph of G is the graph whose vertices are the proper `k`-colourings of `G`, with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the `(d+2)`-reconfiguration graph of any `d`-degenerate graph on `n` vertices is `O(n^2)`. So far, the existence of a polynomial diameter is open even for `d=2`. In this paper, we prove that the diameter of the k-reconfiguration graph of a `d`-degenerate graph is `O(n^{d+1})` for `k \ge d+2`. Moreover, we prove that if ` k \ge \frac 32(d+1)` then the diameter of the `k`-reconfiguration graph is quadratic, improving the previous bound of `k \ge 2d+1`. We also show that the `5`-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.

M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi , A. Mary , M. Mühlenthaler et K. Wasa, The Perfect Matching Reconfiguration Problem

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as `P_4`-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

V. Dujmović, L. Esperet, G. Joret, B. Walczak, et D.R. Wood, Planar graphs have bounded nonrepetitive chromatic number

A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.


N. Bousquet, W. Cames van Batenburg, L. Esperet, G. Joret, W. Lochet, C. Muller, et F. Pirot, Packing and covering balls in graphs excluding a minor

We prove that for every integer `t >=1` there exists a constant `c_t` such that for every `K_t`-minor-free graph `G`, and every set `S` of balls in `G`, the minimum size of a set of vertices of `G` intersecting all the balls of `S` is at most `c_t` times the maximum number of vertex-disjoint balls in `S`. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.



L. Esperet et M. Stehlík, Bipartite complements of circle graphs
Discrete Mathematics 343(6) (2020), 111834.

Using an algebraic characterization of circle graphs, Bouchet proved in 1999 that if a bipartite graph `G` is the complement of a circle graph, then `G` is a circle graph. We give an elementary proof of this result.

arXiv:1910.08388 doi:10.1016/j.disc.2020.111834


E. Bamas et L. Esperet, Local approximation of the Maximum Cut in regular graphs
45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least `1/2` in average. When the graph is `d`-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MAXCUT in regular graphs. We first prove that if `G` is `d`-regular, with `d` even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of `1/d` for `d`-regular graphs with `d` odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio `1/d+\epsilon` (with `\epsilon>0`) can run in a constant number of rounds. We also prove results of a similar flavour for the MAXDICUT problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.