Well-Quasi-Order of Relabel Functions

We define NLC _k^ℱ to be the restriction of the class of graphs NLC k , where relabelling functions are exclusively taken from a set ℱ of functions from 1,..., k into 1,..., k . We characterize the sets of functions ℱ for which NLC _k^ℱ is well-quasi-ordered by the induced subgraph relation ≤ i . Precisely, these sets ℱ are those which satisfy that for every f,g∈ℱ , we have Im ( f ∘ g ) = Im ( f ) or Im ( g ∘ f ) = Im ( g ). To obtain this, we show that words (or trees) on ℱ 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^ℱ for some family ℱ . This would imply Pouzet’s conjecture.