Brakensiek–Guruswami's approximate graph homomorphism hardness conjecture
Statement
Let and be non-bipartite loopless undirected graphs such that . The Brakensiek–Guruswami conjecture asserts that
is -hard. Here is the approximate graph homomorphism problem distinguishing instances homomorphic to from instances not homomorphic to . This is presented as a stronger conjecture than the approximate graph-colouring conjecture; the source identifies graphs with loops or bipartite graphs as trivial or reducible to -colouring, while the stated non-bipartite loopless case remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.