The subdivision conjecture for K4K_4

Let K4K_4 be the complete graph on four vertices, and let a subdivision be a graph obtained by replacing edges by paths. A graph is SPN if it is the sum of a positive semidefinite matrix and a nonnegative matrix.

Subdivision conjecture for K4K_4. Every subdivision of K4K_4 in which all six edges were subdivided, each at least once, is SPN.

The conjecture concerns the remaining subdivisions of K4K_4 in the proposed characterization of SPN graphs. The source states that the case in which each edge is subdivided once is unresolved and does not provide a resolution of the general conjecture.

Sources & referencesView supporting material

Primary source

Naomi Shaked-Monderer, “SPN graphs: when copositive=SPN”, arXiv:1604.02172 (2016).

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.