The extremal K4K_4-free graph conjecture for fractional separation dimension

At least 9 years old · documented by

Let GG be an nn-vertex graph that does not contain K4K_4, and let πf(G)\pi_f(G) denote its fractional separation dimension. For n≥10n\ge 10, consider the complete tripartite graph

K1,⌊(n−1)/2⌋,⌈(n−1)/2⌉.K_{1,\lfloor (n-1)/2\rfloor,\lceil (n-1)/2\rceil}.

The extremal K4K_4-free graph conjecture. For n≥10n\ge 10, the nn-vertex graph not containing K4K_4 that maximizes πf\pi_f is K1,⌊(n−1)/2⌋,⌈(n−1)/2⌉K_{1,\lfloor (n-1)/2\rfloor,\lceil (n-1)/2\rceil}. The conjecture is motivated by computations verifying the extremum among tripartite graphs up to 1414 vertices, while the supplied text does not establish the claim for all n≥10n\ge 10.

References

Primary source

Sarah J. Loeb and Douglas B. West, “Fractional and Circular Separation Dimension of Graphs”, arXiv:1609.01612 (2016).

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.