Jamison and Sprague's threshold-number conjecture for graphs and their complements

For a finite graph GG, let Θ(G)\Theta(G) be its threshold number, the smallest positive integer kk such that GG is a kk-threshold graph, and let GcG^c denote its complement.

Jamison and Sprague's conjecture. For every integer k1k\ge 1, there is a graph GG with

Θ(G)=2kandΘ(Gc)=2k+1.\Theta(G)=2k \quad\text{and}\quad \Theta(G^c)=2k+1.

Jamison and Sprague established that the threshold numbers of a graph and its complement differ by at most one, with the parity determining which value can occur. Chen and Hao gave a partial solution by determining the threshold numbers of complete multipartite graphs whose parts are not small and of their complements; the stated existence claim is resolved according to the supplied status evidence.

Sources & referencesView supporting material

Primary source

Runze Wang, “Threshold numbers of some graphs”, arXiv:2406.12063 (2024).

Additional references

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

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.