Sharpness of the edge-distinguishing bound for infinite locally finite star-free graphs

From papers

Let nn be a natural number greater than three. A connected infinite locally finite graph is a graph with infinitely many vertices, finite vertex degrees, and a path between every pair of vertices; for a graph GG, let D(G)D'(G) denote its distinguishing index, the least number of colours in an edge colouring preserved only by the identity automorphism.

Sharpness conjecture. For every natural number nn greater than three there exists a connected infinite locally finite graph GG such that

D(G)=n1.D'(G)=n-1.

The conjecture asks whether the upper bound D(G)n1D'(G)\leqslant n-1 for connected locally finite K1,nK_{1,n}-free graphs is attained for every n4n\geqslant4 in the infinite case. The paper notes that the bound is attained for finite graphs and for infinite locally finite K1,3K_{1,3}-free graphs, while the cases n>3n>3 remain open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Marcin Stawiski, “Distinguishing infinite star-free graphs”, arXiv:2102.00779 (2021).

Solutions 0

No solutions have been posted yet.