Győri–Paulos–Salia–Tompkins–Zamora planar forbidden-subgraph counting conjecture
Győri–Paulos–Salia–Tompkins–Zamora planar forbidden-subgraph counting conjecture
Let be a finite set of graphs, let be a graph, and let be the class of all planar graphs with no subgraph isomorphic to any member of . Assume that . Győri–Paulos–Salia–Tompkins–Zamora's conjecture. There is an integer such that
This conjecture concerns the polynomial order of homomorphism and subgraph counts in planar graph classes with finitely many forbidden subgraphs. The paper notes that its bounded-expansion theorem gives a negative answer to a related question, but does not state a resolution of this conjecture.
Sources & referencesView supporting material
Primary source
Chun-Hung Liu, “Homomorphism counts in robustly sparse graphs”, arXiv:2107.00874 (2021).
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.