Connectivity threshold conjecture for honest connected colorings
Connectivity threshold conjecture for honest connected colorings
Let be an honest property of sequences, meaning that it is inherited by every nonempty block, is preserved under concatenation of sequences over disjoint color sets, and admits arbitrarily long sequences over a finite alphabet. Let be the least alphabet size for which arbitrarily long sequences with property exist, and let be the minimum number of colors in a -connected coloring of .
Connectivity threshold conjecture for honest connected colorings. For every honest property , there exists a constant such that every -connected graph satisfies
The claim asks whether sufficiently high connectivity always permits the optimal sequence alphabet size. The paper gives a related bound for -connected graphs, but leaves this stronger formulation open.
Sources & referencesView supporting material
Primary source
Michał Dębski, Jarosław Grytczuk, Paweł Naroski and Małgorzata Śleszyńska-Nowak, “Strongly proper connected coloring of graphs”, arXiv:2301.10578 (2023).
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.