The planar maximum-degree-four characterization of semi-transitive line graphs

From papers

Let GG be a graph, let L(G)L(G) denote its line graph, and let Δ(G)\Delta(G) denote its maximum degree. An orientation is semi-transitive when it is acyclic and has no shortcuts. Planar line-graph characterization. The line graph L(G)L(G) is semi-transitively orientable if and only if GG is planar and Δ(G)4\Delta(G)\leq 4.

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

No solutions have been posted yet.