2021/08/05 by M M Akbar, Akbar, M M, Prosper D. Akrobotu +3 · 1 citation
Computer Science · Engineering · #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Formal Methods in Verification #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2108.02363
openalex publication_date 2021/08/05 · openalex created_date 2021/08/16 · openalex updated_date 2026/07/28
An open question in the theory of word-representable graphs for the past decade has been whether the line graph of a non-word-representable graph is always non-word-representable. By formulating an appropriate optimization problem for the decision problem of 3-semi-transitive graphs, we show that the line graph of a non-word-representable graph can be word-representable. Using IBM's CPLEX solver, we demonstrate for several known word-representable and non-word-representable graphs that the line graph of a graph is 3-semi-transitive when there is a solution to the optimization problem. This results in an example where the line graph of a non-word-representable graph is both 3-semi-transitive and semi-transitive and thus is word-representable.