Jamison and Sprague's threshold-number conjecture for graphs and their complements
Jamison and Sprague's threshold-number conjecture for graphs and their complements
For a finite graph , let be its threshold number, the smallest positive integer such that is a -threshold graph, and let denote its complement.
Jamison and Sprague's conjecture. For every integer , there is a graph with
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.