The maximum partial-dual genus bound for planar graphs

Let GG be a planar graph, let GcG^c denote its complement, let χ(Gc)\chi(G^c) be the chromatic number of GcG^c, and let yGy_G denote the maximum genus among partial duals of GG. For an integer λ\lambda, say that GG is λ\lambda-edge-connected if every edge cut of GG has size at least λ\lambda.

Maximum partial-dual genus conjecture. If G≇C3G\not\cong C_3 is a λ\lambda-edge-connected planar graph with λ{1,2}\lambda\in\{1,2\}, then

yG2χ(Gc)λ+1.y_G\leq 2\chi(G^c)-\lambda+1.

This conjecture proposes a chromatic-number bound for the maximum partial-dual genus in the cases of 1- and 2-edge-connected planar graphs, where the authors report that they have not found graphs attaining the previously obtained bound. The even paths and even cycles discussed immediately before the conjecture satisfy the proposed inequality.

Sources & referencesView supporting material

Primary source

Jiaying Chen, Xian'an Jin and Gang Zhang, “On the maximum partial-dual genus of a planar graph”, arXiv:2503.20329 (2025).

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.