Borozan et al.'s conjecture on k-proper partitions
Borozan et al.'s conjecture on k-proper partitions
Let be a graph of order , and let be an integer at least . A partition of is -proper if every part induces a -connected subgraph of , where a graph is -connected if it has more than vertices and deleting any set of fewer than vertices leaves it connected. Write for the minimum degree of . Borozan et al.'s conjecture. If
then has a -proper partition satisfying
This would improve the known bound with constant in the corresponding minimum-degree theorem, reducing that constant to and sharpening the bound on the number of parts.
Sources & referencesView supporting material
Primary source
Michitaka Furuya, Masaki Kashima and Katsuhiro Ota, “New Invariants for Partitioning a Graph into 2-connected Subgraphs”, arXiv:2403.08465 (2024).
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.