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

From papers

Let HH be a connected core on k3k\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

NEQkEH.\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.

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

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).

Solutions 0

No solutions have been posted yet.