Characterizations and Properties of Word-representable Graph Classes

Abstract

A graph G with vertex set V (G) and edge set E(G) is said to be word-representable if there exists a word w over the alphabet V (G) such that, for any two distinct letters x, y ∈ V (G), the letters x and y alternate in w if and only if xy ∈ E(G).