The degree-four planar line-graph conjecture
Let be a graph, let denote its line graph, and let denote its maximum degree. A graph is word-representable if it admits a word representation, and an orientation is -semi-transitive when it satisfies the corresponding -semi-transitivity condition. Degree-four line-graph conjecture. The line graph of a graph with is at least 3-semi-transitively orientable. Moreover, if is non-word-representable, , and is planar, then 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
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.