Word-representable graph
 | This article, Word-representable graph, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
In graph theory, 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 the edge xy is in E. Letters x and y alternate in 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). Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. Various generalisations of the theory of word-representable graphs accommodate representation of any graph.
References
- S. Kitaev. A comprehensive introduction to the theory of word-representable graphs. In: E. Charlier, J. Leroy, M. Rigo (eds), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36-67.
- S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015. ISBN 978-3-319-25859-1