Well-Quasi-Order of Relabel Functions
Well-Quasi-Order of Relabel Functions
复制标题
重新标记函数的良拟序
DOI：
10.1007/s11083-010-9174-0
复制
发表时间：
2010
期刊：
影响因子：
0.4
通讯作者：
Stéphan Thomassé
中科院分区：
文献类型：
--
作者：
J. Daligault;M. Rao;Stéphan Thomassé
We define NLC$_k^{\mathcal{F}}$ to be the restriction of the class of graphs NLCk, where relabelling functions are exclusively taken from a set $\mathcal{F}$ of functions from {1,...,k} into {1,...,k}. We characterize the sets of functions $\mathcal{F}$ for which NLC$_k^{\mathcal{F}}$ is well-quasi-ordered by the induced subgraph relation ≤ i. Precisely, these sets $\mathcal{F}$ are those which satisfy that for every $f,g\in \mathcal{F}$, we have Im(f ∘ g) = Im(f) or Im(g ∘ f) = Im(g). To obtain this, we show that words (or trees) on $\mathcal{F}$ are well-quasi-ordered by a relation slightly more constrained than the usual subword (or subtree) relation. A class of graphs is n-well-quasi-ordered if the collection of its vertex-labellings into n colors forms a well-quasi-order under ≤ i, where ≤ i respects labels. Pouzet (C R Acad Sci, Paris Sér A–B 274:1677–1680, 1972) conjectured that a 2-well-quasi-ordered class closed under induced subgraph is in fact n-well-quasi-ordered for every n. A possible approach would be to characterize the 2-well-quasi-ordered classes of graphs. In this respect, we conjecture that such a class is always included in some well-quasi-ordered NLC$_k^{\mathcal{F}}$ for some family $\mathcal{F}$. This would imply Pouzet’s conjecture.
We define NLC$_k^{\mathcal{F}}$ to be the restriction of the class of graphs NLCk, where relabelling functions are exclusively taken from a set $\mathcal{F}$ of functions from {1,...,k} into {1,...,k}. We characterize the sets of functions $\mathcal{F}$ for which NLC$_k^{\mathcal{F}}$ is well-quasi-ordered by the induced subgraph relation ≤ i. Precisely, these sets $\mathcal{F}$ are those which satisfy that for every $f,g\in \mathcal{F}$, we have Im(f ∘ g) = Im(f) or Im(g ∘ f) = Im(g). To obtain this, we show that words (or trees) on $\mathcal{F}$ are well-quasi-ordered by a relation slightly more constrained than the usual subword (or subtree) relation. A class of graphs is n-well-quasi-ordered if the collection of its vertex-labellings into n colors forms a well-quasi-order under ≤ i, where ≤ i respects labels. Pouzet (C R Acad Sci, Paris Sér A–B 274:1677–1680, 1972) conjectured that a 2-well-quasi-ordered class closed under induced subgraph is in fact n-well-quasi-ordered for every n. A possible approach would be to characterize the 2-well-quasi-ordered classes of graphs. In this respect, we conjecture that such a class is always included in some well-quasi-ordered NLC$_k^{\mathcal{F}}$ for some family $\mathcal{F}$. This would imply Pouzet’s conjecture.