Sharpness of the edge-distinguishing bound for infinite locally finite star-free graphs
Sharpness of the edge-distinguishing bound for infinite locally finite star-free graphs
Let 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 , let 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 greater than three there exists a connected infinite locally finite graph such that
The conjecture asks whether the upper bound for connected locally finite -free graphs is attained for every in the infinite case. The paper notes that the bound is attained for finite graphs and for infinite locally finite -free graphs, while the cases 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
Sign in to submit a solution.
No solutions have been posted yet.