ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a possibly infinite graph and let r⩾3r\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.