Minor-separating graph-pair conjecture
Minor-separating graph-pair conjecture
Let be a connected graph, and let and be graphs. Write for the number of homomorphisms from to . Minor-separating graph-pair conjecture. For every connected graph , there exist graphs and such that
and
Equivalently, if is the family of graphs not containing as a minor, then but the homomorphism counts from differ. The paper describes this as one of four equivalent open conjectures and regards it as the most approachable.
Sources & referencesView supporting material
Primary source
David E. Roberson, “Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree”, arXiv:2206.10321 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.