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

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 m2m\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.

Sources & referencesView supporting material

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.