Locally series-parallel graph characterization conjecture
Locally series-parallel graph characterization conjecture
Let be a possibly infinite graph and let be an integer. A graph is -locally series-parallel when each of its -balls is series-parallel, and an -local subdivision of a wheel or of is a subdivision of a wheel or contained in for some vertex of . Let denote the -local cover of .
Locally series-parallel graph characterization conjecture. The following are equivalent:
- is -locally series-parallel.
- does not contain an -local subdivision of a wheel or of a .
- is series-parallel.
This conjecture seeks a characterization of locally series-parallel graphs analogous to the corresponding characterizations for locally acyclic and locally chordal graphs. Series-parallel graphs are precisely the graphs of treewidth at most , while the conjectured forbidden local subdivisions reflect the role of and wheels in this setting. The source provides no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Tara Abrishami, Paul Knappe and Jonas Kobler, “Locally chordal graphs”, arXiv:2501.17320 (2025).
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.