Well-Quasi-Order of Relabel Functions

Jean Daligault 1 Michael Rao 2 Stéphan Thomassé 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We define NLC Fk to be the restriction of the class of graphs NLC k , where relabelling functions are exclusively taken from a set F of functions from {1,...,k} into {1,...,k}. We characterize the sets of functions F for which NLC Fk is well-quasi-ordered by the induced subgraph relation ≤ i . Precisely, these sets F are those which satisfy that for every f,g∈F , we have Im(f ∘ g) = Im(f) or Im(g ∘ f) = Im(g). To obtain this, we show that words (or trees) on 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 Fk for some family F . This would imply Pouzet's conjecture.
Type de document :
Article dans une revue
Order, Springer Verlag, 2010, 27, pp.301-315. 〈10.1007/s11083-010-9174-0〉
Liste complète des métadonnées

Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 13:45:14
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13



Jean Daligault, Michael Rao, Stéphan Thomassé. Well-Quasi-Order of Relabel Functions. Order, Springer Verlag, 2010, 27, pp.301-315. 〈10.1007/s11083-010-9174-0〉. 〈lirmm-00806804〉



Consultations de la notice