The Okrasa–Rzążewski conjecture on indecomposable graph cores
Let be a connected core on vertices. Write for the edge relation of , let denote the relational clone generated by , and let be the -ary disequality relation. Okrasa–Rzążewski conjecture. is indecomposable if and only if
The paper verifies this conjecture for graphs with at most vertices. Whether it holds for graphs with more than 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.