Gallai's conjecture for chordal graphs with subdivided caterpillar representations
Gallai's conjecture for chordal graphs with subdivided caterpillar representations
Let be a connected chordal graph admitting a tree representation , where is a subdivided caterpillar. Subdivided-caterpillar Gallai conjecture. Then
This asserts that every such graph has a single-vertex longest path transversal. It is a restricted version of the broader open problem asking whether every connected chordal graph satisfies ; the supplied text does not state whether this restricted claim is resolved.
Sources & referencesView supporting material
Primary source
James A. Long, Kevin G. Milans and Michael C. Wigal, “Longest Path and Cycle Transversals in Chordal Graphs”, arXiv:2412.20729 (2024).
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.