The component-deletion conjecture for inherent two-rooted graphs

A two-rooted graph (H,s,t)(H,s,t) is a graph HH with two distinguished vertices ss and tt. It is inherent if every graph containing a copy of HH also contains an avoidable copy of (H,s,t)(H,s,t). For graphs HH and HH', write H+HH+H' for their disjoint union, and suppose that s,ts,t are vertices of HH.

Component-deletion conjecture. If (H+H,s,t)(H+H',s,t) is inherent and s,ts,t are in HH, then (H,s,t)(H,s,t) is also inherent.

Together with the component-separation conjecture, this addresses which disconnected two-rooted graphs can be inherent. The source does not provide a resolution.

Sources & referencesView supporting material

Primary source

Vladimir Gurvich, Matjaž Krnc, Martin Milanič and Mikhail Vyalyi, “Avoidability beyond paths”, arXiv:2208.12803 (2025).

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.