On representable graphs

Tools

Kitaev, Sergey and Pyatkin, Artem (2008) On representable graphs. Journal of Automata, Languages and Combinatorics, 13 (1). pp. 45-54. (https://doi.org/10.25596/jalc-2008-045)

[thumbnail of Kitaev-Pyatkin-JALC-2008-On-representable-graphs]
Preview
 Text. Filename: Kitaev_Pyatkin_JALC_2008_On_representable_graphs.pdf
Accepted Author Manuscript
Download (249kB)| Preview

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)