Letter graphs and well-quasi-order by induced subgraphs
type: Item
instance of: scholarly article
title: Letter graphs and well-quasi-order by induced subgraphs
zbMATH Open document ID: 0997.05086
DOI: 10.1016/S0012-365X(01)00094-2
published in: Discrete Mathematics
publication date: 2002-05-21T00:00:00Z
review text: All graphs \(G= (V,E)\) considered in this paper are undirected and simple ones. For a given word \(w\) over an alphabet and a set of ordered pairs of letters which define adjacencies the letter graph of \(w\) is constructed. Such graphs \(G\) over some alphabet of size \(k\) are called \(k\)-letter graphs. The lettericity \(\ell(G)\) of a graph \(G\) is the least size of the alphabet that suffices to represent \(G\) as a letter graph. The cycle \(C_6\) is given as a 3-letter graph with \(\ell(C_6)\leq 3\). In Chapter 3 the author gets basic properties of \(k\)-letter graphs, especially necessary and sufficient conditions for \(G\) to be a \(k\)-letter graph (Proposition 1), and from this it follows that 2-letter graphs are bipartite, split, or cobipartite graphs. In Chapter 4 cobipartite 2-letter graphs are characterized as unbounded interval graphs and split 2-letter graphs as threshold graphs, and from these results follows that the class of 2-letter graphs consists of threshold graphs, unbounded interval graphs, and their complements. Further, the author proves that 2-letter graphs can be recognized in polynomial time. Chapter 5 yields the following statements about the values of the lettericities \(\ell\) for cycles \(C_n\) and paths \(P_n\), namely (1) \(\ell(C_n)= \lfloor(n+ 4)/3\rfloor\) for \(n\geq 4\); (2) \(\lfloor(n+ 1)/3\rfloor\leq \ell(P_n)\leq \lfloor(n+4)/3)\rfloor\). The following is conjectured: If \(n\geq 3\) then \(\ell(P_n)= \lfloor(n+ 4)/3\rfloor\). It is proved that for large \(n\) there are \(n\)-vertex graphs whose lettericity exceeds \(0,707\cdot n\). In the final Chapter 6 it is shown 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. Further, it is proved that for any fixed \(k\) the class of \(k\)-letter graphs can also be recognized in polynomial time. Three open problems are formulated.
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1743036
zbMATH Keywords: well-quasi-order
zbMATH Keywords: lettericity
zbMATH Keywords: \(k\)-letter graph
zbMATH Keywords: interval graphs
zbMATH Keywords: threshold graphs
zbMATH Keywords: subgraph relation
author: Marko Petkovšek
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
Recommended article: Induced subgraphs and well‐quasi‐ordering
Recommended article: Labelled induced subgraphs and well-quasi-ordering
Recommended article: Subgraphs and well‐quasi‐ordering
Recommended article: Bipartite induced subgraphs and well-quasi-ordering
Recommended article: Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Recommended article: Two forbidden induced subgraphs and well-quasi-ordering
Recommended article: The induced subgraph order on unlabelled graphs
Recommended article: Q3220637
Recommended article: Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs
Recommended article: The quasi order of graphs on an ordinal
description: scientific article; zbMATH DE number 1743036