Existence of graphs of every prescribed minimum girth without the AOP property
Existence of graphs of every prescribed minimum girth without the AOP property
Let . 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 , there exist graphs with girth greater than or equal to 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
Sign in to submit a solution.
No solutions have been posted yet.