Letter graphs and well-quasi-order by induced subgraphs
Letter graphs and well-quasi-order by induced subgraphs
复制标题
DOI：
10.1016/s0012-365x(01)00094-2
复制
发表时间：
2002-02-06
影响因子：
0.8
通讯作者：
Petkovsek, M
中科院分区：
文献类型：
--
作者：
Petkovsek, M
给定有限字母表上的一个词w和一组定义邻接关系的有序字母对，我们构造一个图，我们称之为w的字母图。图G的字母度是使图G成为字母图的字母表的最小长度。这组2字母图包括阈值图、无界区间图和它们的补图。我们确定了循环的字母性，并将路径的字母性限制在长度为1的区间内。通过导出子图关系证明了这类k-字母图是良准序的，并且它具有有限的最小禁止导出子图集。因此，对于任何固定的k，k字母图都可以在多项式时间内识别。(C)2002 Elsevier Science B. V.保留所有权利。
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. (C) 2002 Elsevier Science B.V. All rights reserved.