Surface bound conjecture for signed graph genus

About 16 years old · traced to

Let SS be a surface, let nSn_S be the largest order of a complete graph that embeds into SS, and let γ(G,σ)\gamma(G,\sigma) and γ∗(G,σ)\gamma^*(G,\sigma) denote the relevant orientable and non-orientable genera of a signed graph. Surface bound conjecture. If SS is not the projective plane, then

γ(G,σ)≤γ(±KS)andγ∗(G,σ)≤γ∗(±KS),\gamma(G,\sigma) \leq \gamma(\pm K_S) \quad\text{and}\quad \gamma^*(G,\sigma) \leq \gamma^*(\pm K_S),

and there are graphs for which equality holds. The statement is presented as a conjecture, with a theorem identified as a first result toward its proof; the supplied text gives no resolution status.

References

Primary source

Eckhard Steffen and Alexander Vogel, “Concepts of signed graph coloring”, arXiv:1909.09381 (2020).

Additional references

2 papers in this index state this conjecture (2010–2019). The statement above is taken from the most recent of them; the others are arXiv:1012.4117.

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.