Characterization of graphs for which the blow-up optimization is unattained

About 5 years old · traced to

Let HH be a graph with no isolated vertices, let kk be a positive integer, and let β(H,k)\beta(H,k) be the optimization parameter defined in the paper. Attainment conjecture for β(H,k)\beta(H,k). The quantity β(H,k)\beta(H,k) is not achieved if and only if k=1k=1 and either H=K1,mH=K_{1,m} or H=mK2H=mK_2 for some m≥2m\geq 2, where mK2mK_2 is the matching on mm edges.

The paper notes that the two listed families are known never to attain the optimum, whereas β(H,k)\beta(H,k) is attained whenever kδ(H)≥2k\delta(H)\geq 2. The conjecture proposes that these are the only exceptions.

References

Primary source

Christopher Cox and Ryan R. Martin, “Counting paths, cycles and blow-ups in planar graphs”, arXiv:2101.05911 (2022).

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.