Quadratic embeddability conjecture for theta graphs

About 2 years old · traced to

Let Θ(α,β,γ)\Theta(\alpha,\beta,\gamma) be the theta graph formed from three internally vertex-disjoint paths of lengths α\alpha, β\beta, and γ\gamma between two common endpoints, where 1≤α≤β≤γ1\leq\alpha\leq\beta\leq\gamma and at most one of α,β,γ\alpha,\beta,\gamma equals 11. A graph is of QE class if it has the quadratic embeddability property.

Quadratic embeddability conjecture. Assume 1≤α≤β≤γ1\leq\alpha\leq\beta\leq\gamma and β≥2\beta\geq2. Then Θ(α,β,γ)\Theta(\alpha,\beta,\gamma) is of QE class if and only if either

α=1,\alpha=1,

or

α=2,β=3,γ is odd.\alpha=2,\qquad \beta=3,\qquad \gamma\text{ is odd}.

The preceding theorems establish the QE and non-QE classifications for several broad families of theta graphs, leaving the stated exceptional case as the remaining classification predicted by the conjecture. The conjecture would give a complete characterization of quadratic embeddability for theta graphs under the indicated ordering and parameter restrictions.

References

Primary source

Wojciech Młotkowski, Marek Skrzypczyk and Michał Wojtylak, “On quadratic embeddability of bipartite graphs and theta graphs”, arXiv:2409.17662 (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.