Connectivity threshold conjecture for honest connected colorings

Let P\mathcal{P} 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 m(P)m(\mathcal{P}) be the least alphabet size for which arbitrarily long sequences with property P\mathcal{P} exist, and let P-c(G)\operatorname{\mathcal{P}-c}(G) be the minimum number of colors in a P\mathcal{P}-connected coloring of GG.

Connectivity threshold conjecture for honest connected colorings. For every honest property P\mathcal{P}, there exists a constant c(P)c(\mathcal{P}) such that every c(P)c(\mathcal{P})-connected graph GG satisfies

P-c(G)m(P).\operatorname{\mathcal{P}-c}(G)\leq m(\mathcal{P}).

The claim asks whether sufficiently high connectivity always permits the optimal sequence alphabet size. The paper gives a related bound for 44-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

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.