2017/05/16 by Sergey Kitaev, Kitaev, Sergey · 7 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.1705.05924
Letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word xyxy⋯ (of even or odd length) or a word yxyx⋯ (of even or odd length). A graph G=(V,E) is word-representable if and only if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy∈ E. Word-representable graphs generalize several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. This paper offers a comprehensive introduction to the theory of word-representable graphs including the most recent developments in the area.