The characterization of locally interval graphs as circular-arc graphs

Given a graph GG and a vertex vv of GG, let BG(v,r/2)B_G(v,r/2) be the subgraph induced by vertices at distance at most r/2\lfloor r/2\rfloor from vv, with edges xyxy satisfying d(v,x)+d(v,y)<rd(v,x)+d(v,y)<r. The graph GG is rr-locally interval if every such ball is an interval graph. A graph is circular-arc if it has a region representation over a cycle in which every region is a path.

Rz\k{a}.{z}ewski's conjecture. Locally interval graphs are exactly circular-arc graphs.

This conjecture proposes that being locally path-like, in the sense that all sufficiently specified local balls are interval graphs, is equivalent to admitting a region representation over a cycle. The source gives no resolution status.

Sources & referencesView supporting material

Primary source

Tara Abrishami, Sandra Albrechtsen, Nathan Bowler, Paul Knappe and Jana Katharina Nickel, “Locally interval graphs are circular-arc graphs”, arXiv:2512.19040 (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.