← All problems

Existence conjecture for non-trivial FF-irregular graphs

1 year old · traced to

Let FF be a connected graph of order at least 33. An FF-irregular graph is a graph in which no two distinct vertices have isomorphic FF-neighbourhoods.

Existence conjecture. For every connected graph FF of order 33 or more, there exists a non-trivial FF-irregular graph.

The conjecture concerns the existence of irregular graphs relative to an arbitrary connected graph FF. It is known for stars and complete graphs of order at least 33, but the general case is not resolved in the supplied text.

References
  1. Tatiana Dovzhenok, Ilya Lukashenko and Yahor Filiuta, “On C_n-irregular oriented graphs”, arXiv:2512.05487 (2026).

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.