The characterization of locally interval graphs as circular-arc graphs
The characterization of locally interval graphs as circular-arc graphs
Given a graph and a vertex of , let be the subgraph induced by vertices at distance at most from , with edges satisfying . The graph is -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
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.