The degree-four planar line-graph conjecture

About 5 years old · traced to

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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.