The degree-four planar line-graph conjecture

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. A graph is word-representable if it admits a word representation, and an orientation is kk-semi-transitive when it satisfies the corresponding kk-semi-transitivity condition. Degree-four line-graph conjecture. The line graph L(G)L(G) of a graph GG with Δ(G)4\Delta(G)\leq 4 is at least 3-semi-transitively orientable. Moreover, if GG is non-word-representable, Δ(G)4\Delta(G)\leq 4, and GG is planar, then L(G)L(G) is word-representable.

The claim proposes relationships between the semi-transitivity and word-representability of a graph and those of its line graph, in the degree-four planar setting. The source presents these as possible relationships rather than established results; their general validity is not resolved there.

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.