Existence of graphs of every prescribed minimum girth without the AOP property

From papers

Let gNg\in\mathbb{N}. A graph has the AOP property if it admits an acyclic orientation with at most one directed path between any pair of vertices, and its girth is the length of its shortest cycle. High-girth AOP conjecture. For every gNg\in\mathbb{N}, there exist graphs with girth greater than or equal to gg that do not have the AOP property. The conjecture challenges the expectation that sufficiently large girth forces the AOP property; the supplied text gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Arpan Sadhukhan, “Shift Graphs, Chromatic Number and Acyclic One-Path Orientations”, arXiv:2308.14010 (2024).

Solutions 0

No solutions have been posted yet.