The extremal K4K_4-free graph conjecture for fractional separation dimension

From papers

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 n10n\ge 10, consider the complete tripartite graph

K1,(n1)/2,(n1)/2.K_{1,\lfloor (n-1)/2\rfloor,\lceil (n-1)/2\rceil}.

The extremal K4K_4-free graph conjecture. For n10n\ge 10, the nn-vertex graph not containing K4K_4 that maximizes πf\pi_f is K1,(n1)/2,(n1)/2K_{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 n10n\ge 10.

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

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

Solutions 0

No solutions have been posted yet.