Blow-up conjecture for inversion diameter

About 2 years old · traced to

Let GG be a graph, let tt be a positive integer, let K‾t\overline{K}_t be the edgeless graph on tt vertices, and let G[K‾t]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[K‾t]))⩽t⋅diam⁡(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.