Cleanliness conjecture for t-clock-free graphs

A hole is an induced cycle on four or more vertices. A t-clock is a clock consisting of a hole CC and a vertex vv such that there are two neighbours x,yV(C)x,y\in V(C) of vv where the distance between xx and yy along CC is at least tt. A graph is t-clock-free if it contains no induced subgraph that is a t-clock. A graph class is clean if there is a function f:NNf:\mathbb{N}\rightarrow\mathbb{N} such that, for every ss, each ss-clean graph GG in the class satisfies tw(G)f(s)\operatorname{tw}(G)\leq f(s). Cleanliness conjecture for t-clock-free graphs. For every fixed t1t\geq 1, the family of t-clock-free graphs is clean. This would strengthen the known result that the class of clock-free graphs is clean and the previously proved cleanliness of the class of (clock, prism, pyramid)-free graphs; whether the stated strengthening holds is left open in the source.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, Sepehr Hajebi and Sophie Spirkl, “Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole”, arXiv:2311.05719 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.