The Okrasa–Rzążewski conjecture on indecomposable graph cores

About 2 years old · traced to

Let HH be a connected core on k≥3k\geq 3 vertices. Write EHE_H for the edge relation of HH, let ⟨EH⟩\langle E_H\rangle denote the relational clone generated by EHE_H, and let NEQk\text{NEQ}_k be the kk-ary disequality relation. Okrasa–Rzążewski conjecture. HH is indecomposable if and only if

NEQk∈⟨EH⟩.\text{NEQ}_k\in\langle E_H\rangle.

The paper verifies this conjecture for graphs with at most 77 vertices. Whether it holds for graphs with more than 77 vertices remains open.

References

Primary source

Ambroise Baril, Miguel Couceiro and Victor Lagerkvist, “The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture”, arXiv:2404.09798 (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.