### Abstract

Original language | English |
---|---|

Pages (from-to) | 45-54 |

Number of pages | 10 |

Journal | Journal of Automata, Languages and Combinatorics |

Volume | 13 |

Issue number | 1 |

Publication status | Published - 2008 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Automata, Languages and Combinatorics*,

*13*(1), 45-54.

}

*Journal of Automata, Languages and Combinatorics*, vol. 13, no. 1, pp. 45-54.

**On representable graphs.** / Kitaev, Sergey; Pyatkin, Artem.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On representable graphs

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - combinatorics on words

KW - representation

KW - (outer)planar graphs

KW - prisms

KW - Perkins semigroup

KW - graph subdivisions

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/repgr.pdf

M3 - Article

VL - 13

SP - 45

EP - 54

JO - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1

ER -