The tree-width two running-time conjecture

Let $H$ be a graph, let ${\mathrm{tw}}(H)$ denote its tree-width, and let $M_H(n)$ denote the maximum running time of the $H$-process. Tree-width two conjecture. Every graph $H$ with

$${\mathrm{tw}}(H)=2$$

has

$$M_H(n)=O(n).$$

Graphs of tree-width one are trees and have constant maximum running time, while complete bipartite graphs $K_{2,s}$ show that tree-width two can already give linear running time. The conjecture asserts that linear growth is the largest possible for tree-width two.