The planar maximum-degree-four characterization of semi-transitive line graphs
The planar maximum-degree-four characterization of semi-transitive line graphs
Let be a graph, let denote its line graph, and let denote its maximum degree. An orientation is semi-transitive when it is acyclic and has no shortcuts. Planar line-graph characterization. The line graph is semi-transitively orientable if and only if is planar and .
This is presented in the paper's conclusion as a conjecture arising from the preceding results. The source does not provide a resolution, so the characterization remains open here.
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
M M Akbar, P D Akrobotu and C P Brewer, “On the Existence of Word-representable Line Graphs of Non-word-representable Graphs”, arXiv:2108.02363 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.