Cleanliness conjecture for t-clock-free graphs
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 and a vertex such that there are two neighbours of where the distance between and along is at least . 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 such that, for every , each -clean graph in the class satisfies . Cleanliness conjecture for t-clock-free graphs. For every fixed , 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
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.