Quadratic embeddability conjecture for theta graphs

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.

Sources & referencesView supporting material

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.