Elsevier

Discrete Mathematics

Volume 244, Issues 1–3, 6 February 2002, Pages 375-388
Discrete Mathematics

Letter graphs and well-quasi-order by induced subgraphs

https://doi.org/10.1016/S0012-365X(01)00094-2Get rights and content
Under an Elsevier user license
open archive

Abstract

Given a word w over a finite alphabet and a set of ordered pairs of letters which define adjacencies, we construct a graph which we call the letter graph of w. The lettericity of a graph G is the least size of the alphabet permitting to obtain G as a letter graph. The set of 2-letter graphs consists of threshold graphs, unbounded-interval graphs, and their complements. We determine the lettericity of cycles and bound the lettericity of paths to an interval of length one. We show that the class of k-letter graphs is well-quasi-ordered by the induced subgraph relation, and that it has a finite set of minimal forbidden induced subgraphs. As a consequence, k-letter graphs can be recognized in polynomial time for any fixed k.

Keywords

Lettericity
Well-quasi-order
Induced subgraph relation

Cited by (0)