Laboratoire des Sciences pour la Conception, l'Optimisation et la Production

Faithful Universal Graphs for Minor-Closed Classes

Abstract. It was proved by Huynh et al. [ Universality in Minor-Closed Graph Classes, preprint, arXiv:2109.00327, 2021] that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We prove a finite, quantitative version of this res...

Determining a graph from its reconfiguration graph

Given a graph G and a natural number k , the k -recolouring graph C k ( G ) is the graph whose vertices are the k -colourings of G and whose edges link pairs of colourings which differ at exactly one vertex of G . Recently, Hogan et al. proved that G can be determined from C k (...