Blow-up conjecture for inversion diameter

From papers

Let GG be a graph, let tt be a positive integer, let Kt\overline{K}_t be the edgeless graph on tt vertices, and let G[Kt]G[\overline{K}_t] denote the blow-up of GG in which each vertex is replaced by an independent set of size tt. Let I(G)\mathcal{I}(G) be the inversion graph of GG. Blow-up conjecture. For every graph GG and every positive integer tt,

diam(I(G[Kt]))tdiam(I(G)).\operatorname{diam}(\mathcal{I}(G[\overline{K}_t])) \leqslant t\cdot\operatorname{diam}(\mathcal{I}(G)).

The conjecture seeks to generalise the paper's upper bound for complete multipartite graphs to blow-ups of arbitrary graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Frédéric Havet, Florian Hörsch and Clément Rambaud, “Diameter of the inversion graph”, arXiv:2405.04119 (2024).

Solutions 0

No solutions have been posted yet.