The lower bound for negative oriented distinguishing index

At least 1 year old · documented by

Let GG be a connected graph. Here D′(G)D'(G) denotes the distinguishing index of GG, and OD′−(G)OD'^-(G) denotes the negative oriented distinguishing index.

Lower-bound conjecture.

OD′−(G)≥⌊D′(G)/2⌋.OD'^-(G)\geq \lfloor D'(G)/2\rfloor.

If true, this would show that a suitable orientation cannot reduce the number of required colours by more than half; in particular, every graph with a rigid orientation would have distinguishing index at most three. The conjecture is open.

References

Primary source

Aleksandra Gorzkowska and Jakub Kwaśny, “Arc-distinguishing of orientations of graphs”, arXiv:2402.16169 (2024).

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.