Locally series-parallel graph characterization conjecture

Let GG be a possibly infinite graph and let r3r\geqslant 3 be an integer. A graph is rr-locally series-parallel when each of its r/2r/2-balls is series-parallel, and an rr-local subdivision of a wheel or of K4K_4 is a subdivision HH of a wheel or K4K_4 contained in BH(v,r/2)B_H(v,r/2) for some vertex vv of HH. Let GrG_r denote the rr-local cover of GG.

Locally series-parallel graph characterization conjecture. The following are equivalent:

  1. GG is rr-locally series-parallel.
  2. GG does not contain an rr-local subdivision of a wheel or of a K4K_4.
  3. GrG_r 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 22, while the conjectured forbidden local subdivisions reflect the role of K4K_4 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

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.