Conditional Lower Bounds

Counting Subgraphs in Degenerate Graphs
A tighter characterization of the subgraphs for which the homomorphism count can be obtained in near-linear time in sparse graphs.
Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira
PDF Arxiv Version
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
A characterization of the pattern subgraphs for which the homomorphism count can be obtained in near-linear time in sparse graphs.
PDF Arxiv Version