The Okrasa–Rzążewski conjecture on indecomposable graph cores
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.
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
Sign in to submit a solution.
No solutions have been posted yet.