ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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)=n−1.D'(G)=n-1.

The conjecture asks whether the upper bound D′(G)⩽n−1D'(G)\leqslant n-1 for connected locally finite K1,nK_{1,n}-free graphs is attained for every n⩾4n\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.