The degree-four planar line-graph conjecture
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.
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.