@inproceedings{b16608e181314f368e0801b01c48cbf7,
title = "Graphs capturing alternations in words",
abstract = "A graph G = (V,E) is representable if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if (x, y) ∈ E for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. A graph is representable if and only if it is k-representable for some k [1].",
keywords = "algorithm analysis, graphs, word patterns",
author = "Magnus Halldorsson and Sergey Kitaev and Artem Pyatkin",
year = "2010",
doi = "10.1007/978-3-642-14455-4_41",
language = "English",
isbn = "978-3-642-14454-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "436--437",
editor = "Yuan Gao and Hanlin Lu and Shinnosuke Seki and Sheng Yu",
booktitle = "Developments in Language Theory",
note = "14th Conference on Dvelopments in Language Theory ; Conference date: 17-08-2010 Through 20-08-2010",
}