@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",

}