On representable graphs

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

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) 2 E for each x 6= y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.
Original languageEnglish
Pages (from-to)45-54
Number of pages10
JournalJournal of Automata, Languages and Combinatorics
Volume13
Issue number1
Publication statusPublished - 2008

Keywords

  • combinatorics on words
  • representation
  • (outer)planar graphs
  • prisms
  • Perkins semigroup
  • graph subdivisions

Cite this