← All problems

Gethner–Sulanke 19-vertex biplanar graph question

Does there exist a biplanar graph G=(V,E)G=(V,E) such that ∣V∣=19|V|=19 and α(G)=2\alpha(G)=2? Here, biplanar means that EE can be partitioned into the edge sets of two planar graphs on the common vertex set VV.

References

Progress summary

Refreshed
Open · solution reported

A new computer-checked argument claims the proposed 1919-vertex graph cannot exist, but independent confirmation is not recorded.

The question asks whether a proposed 1919-vertex biplanar graph configuration exists. The retrieved material reports a negative answer via structural reduction and exhaustive computation.

September 2026 development

Stefan Szeider's paper Biplanar graphs with independence number two are 99-colorable reports that a structural reduction and certified SAT enumeration exclude the proposed configuration.

Current status (as of September 2026): The proposed 1919-vertex configuration is claimed impossible, but the reported computational proof has not been independently verified.

Sources

Solutions 0

No solutions have been posted yet.